提示: 欢迎访问OurACM平台。
Problem 1916 Harmonious Substring Function

Accept: 63    Submit: 245
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A substring of a string T=t1…tn is a string T’=t1+i…tm+i, where 0≤i and m+i≤n. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. For a string S, we define H(S) as harmonious substring function and the value of H(S) is the number of different substrings of S.

For example, the string “aab” only has five different substrings: “a”, “b”, “aa”, “ab”, “aab”, so the value of H(“aab”) is 5. Now given n empty string s0,s1,…,sn-1. Your task is to simulate the following two kinds of operations:

 I i c: Push the character c in the front of the i-th string si (0 ≤ i < n, c is a lowercase letter);

 S i j: Output the sum of the harmonious substring function from the i-th string si to the j-th string sj (inclusive) (0 ≤ i ≤ j < n), that is

Input

The first line of the input contains an integer T (T <= 20), indicating the number of cases. Each case begins with a line containing two integers n and q (1≤n≤50,000, 1≤q≤50,000), the number of strings and the number of operations. Each of the following q lines contains an operation that is said above.

Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answer, one on each line. The output is generated by the operation “S i j”.

Sample Input

2 2 6 I 0 a S 0 1 I 1 b I 1 a I 1 a S 0 1 50000 1 S 0 50000

Sample Output

Case 1: 1 6 Case 2: 0

Source

2010年全国大学生程序设计邀请赛(福州)

Submit  Back  Status  Discuss