AT_abc415_f [ABC415F] Max Combo

There is a string $ S $ of length $ N $ consisting of lowercase English letters. Process a total of $ Q $ queries as follows: - Type $ 1 $ : Change the $ i $ -th character of $ S $ to $ x $ . - Type $ 2 $ : Let $ t $ be the substring of the current $ S $ from the $ l $ -th character through the $ r $ -th character. Find $ f(t) $ defined as follows for this string: - $ f(t) $ is the maximum length of consecutive identical characters in $ t $ . - More precisely, when choosing integers $ a,b $ such that $ 1 \le a \le b \le |t| $ and all characters from the $ a $ -th through the $ b $ -th character of $ t $ are equal, $ f(t) $ is the maximum possible value of $ b-a+1 $ . - For example, $ f( $ `aaaccbbbb` $ )=4 $ , $ f( $ `bbaaabb` $ )=3 $ , $ f( $ `x` $ )=1 $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ S $ $ \rm{Query} $ $ _1 $ $ \rm{Query} $ $ _2 $ $ \vdots $ $ \rm{Query} $ $ _Q $ Here, $ \rm{Query} $ $ _i $ represents the $ i $ -th query. Type $ 1 $ queries are given in the following format: > 1 $ i $ $ x $ Type $ 2 $ queries are given in the following format: > 2 $ l $ $ r $

Every time a type $ 2 $ query appears, output the answer on one line. The use of fast input and output methods is recommended because of potentially large input and output.

### Sample Explanation 1 This input contains five queries. - Initially, the string $ S $ is `babaacczcc`. - The $ 1 $ st query is type $ 2 $ with $ l=1,r=4 $ . - The extracted string is `baba`, and $ f( $ `baba` $ )=1 $ . - The $ 2 $ nd query is type $ 1 $ with $ i=3,x= $ `a`. - The string $ S $ after the change is `baaaacczcc`. - The $ 3 $ rd query is type $ 2 $ with $ l=1,r=10 $ . - The extracted string is `baaaacczcc`, and $ f( $ `baaaacczcc` $ )=4 $ . - The $ 4 $ th query is type $ 1 $ with $ i=8,x= $ `c`. - The string $ S $ after the change is `baaaaccccc`. - The $ 5 $ th query is type $ 2 $ with $ l=1,r=10 $ . - The extracted string is `baaaaccccc`, and $ f( $ `baaaaccccc` $ )=5 $ . ### Sample Explanation 2 The output may be empty. ### Constraints - $ N $ is an integer between $ 1 $ and $ 5 \times 10^5 $ , inclusive. - $ S $ is a string of length $ N $ consisting of lowercase English letters. - $ Q $ is an integer between $ 1 $ and $ 5 \times 10^5 $ , inclusive. - Type $ 1 $ queries satisfy the following constraints: - $ i $ is an integer between $ 1 $ and $ N $ , inclusive. - $ x $ is a lowercase English letter. - Type $ 2 $ queries satisfy the following constraints: - $ l,r $ are integers satisfying $ 1 \le l \le r \le N $ .