CONSEC - Consecutive Letters


You are given a string S containing only uppercase English letters. There are Q queries. Each query can be of two types:

  • 1 i: Find the maximum size of the segment [b, e] where 0 ≤ b ≤ i ≤ e < |S| and substring S[b...e] contains only the letter S[i]. A Substring is a contiguous sequence of characters in a string.
  • 2 i: Change the character in index i with the character ‘#’.

For both type of queries, S[i] will not contain the character ‘#’.The characters of the string are indexed from 0.

Input

The first line contains number of test cases T (1 ≤ T ≤ 15).

For each test cases, the first line contains the string S (1 ≤ |S| ≤ 200000). The 2nd line contains number of queries Q (1 ≤ Q ≤ 100000). Each of the next Q lines contains one query in the format mentioned in the problem statement.

Output

For each test case, first print the test case number, and then the output of every query of type 1 in a new line.

Sample

Input
2
AABBBCCCC
5
1 0
2 1
1 0
2 2
1 3
XXYYY
3
1 3
2 3
1 2

Output
Case 1:
2
1
2
Case 2:
3
1

Warning: The input file is huge, please use fast I/O.

Note: The dataset and time limit have been modified to fit SPOJ.


hide comments
muddglob: 2023-08-24 12:23:06

why i got TLE!!!

prasoonjha1: 2023-04-07 09:45:47

Using Union_find but getting WA on test case 6. What could be the reasons?
Never mind. Should have read question more carefully. It's done now.

Last edit: 2023-04-07 14:35:05
mohan7575: 2022-03-01 17:39:47

weak testcases my q*n solution got AC

asandikci: 2021-12-03 10:05:50

don't forget use fast I/O (like ios::sync_with_stdio(false); cin.tie(0);)
simple Set+pair+lower_bound question

Jean-Ralph Aviles: 2021-08-22 17:26:59

Fast I/O is needed to avoid TLE.

ak748392: 2021-04-07 17:35:59

@shivam_2020 ROFL

asanyal122: 2020-05-17 04:44:41

Union_Find + think reverse

ajaygupta007: 2020-05-08 20:42:43

read problem carefully.I understand this problem after reading more than 10 times .

zakir068: 2020-04-30 12:10:39

NC problem.use dsu + set.

itssanat: 2020-04-25 10:49:09

AC without fast I/O. print as give in sample output format.


Added by:Shafaet
Date:2019-03-20
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own, MIST Inter University Contest