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 sequences 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.



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.



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


Sample Input                 Output for Sample Input




1 0

2 1

1 0

2 2

1 3



1 3

2 3

1 2

Case 1:




Case 2:




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


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

hide comments
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.

immim: 2020-04-17 19:00:49

You got the problem statement that means you've solved 80% -_- -_-

shivam_2020: 2020-03-27 10:46:06

Explaination is as clear as your future.

sahil1422: 2019-12-18 08:13:22

The output format is so confusing. Why can't a clear explanation be provided?
"Case i:" is to be printed or only "i" i.e. case number?

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