AT_abc415_f [ABC415F] Max Combo

長さ $ N $ の英小文字からなる文字列 $ S $ があります。以下のクエリを全部で $ Q $ 個処理してください。 - タイプ $ 1 $ : $ S $ の $ i $ 文字目を $ x $ に変更する。 - タイプ $ 2 $ : 現時点の $ S $ の $ l $ 文字目から $ r $ 文字目までを抜き出した文字列を $ t $ とする。この文字列に対して次のように定義される $ f(t) $ を求めよ。 - $ f(t) $ は $ t $ 中の同じ文字の連続の最大長である。 - 厳密には、 $ 1 \le a \le b \le |t| $ かつ $ t $ の $ a $ 文字目から $ b $ 文字目までが全て等しいような整数 $ a,b $ を選ぶとき、 $ f(t) $ は $ b-a+1 $ の値としてありうる最大値である。 - 例えば $ f( $ `aaaccbbbb` $ )=4 $ 、 $ f( $ `bbaaabb` $ )=3 $ 、 $ f( $ `x` $ )=1 $ である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ S $ $ \rm{Query} $ $ _1 $ $ \rm{Query} $ $ _2 $ $ \vdots $ $ \rm{Query} $ $ _Q $ 但し、 $ \rm{Query} $ $ _i $ は $ i $ 個目のクエリを表す。 タイプ $ 1 $ のクエリは以下の形式で与えられる。 > 1 $ i $ $ x $ タイプ $ 2 $ のクエリは以下の形式で与えられる。 > 2 $ l $ $ r $

タイプ $ 2 $ のクエリが現れる度に、その解答を $ 1 $ 行に出力せよ。 なお、入出力が大きくなる場合があるので、高速な方法で入出力を行うことを推奨する。

### Sample Explanation 1 この入力には $ 5 $ 個のクエリが含まれます。 - はじめ、文字列 $ S $ は `babaacczcc` です。 - $ 1 $ 番目のクエリはタイプ $ 2 $ で、 $ l=1,r=4 $ です。 - 抜き出した文字列は `baba` であり、 $ f( $ `baba` $ )=1 $ です。 - $ 2 $ 番目のクエリはタイプ $ 1 $ で、 $ i=3,x= $ `a` です。 - 変更後の文字列 $ S= $ `baaaacczcc` です。 - $ 3 $ 番目のクエリはタイプ $ 2 $ で、 $ l=1,r=10 $ です。 - 抜き出した文字列は `baaaacczcc` であり、 $ f( $ `baaaacczcc` $ )=4 $ です。 - $ 4 $ 番目のクエリはタイプ $ 1 $ で、 $ i=8,x= $ `c` です。 - 変更後の文字列 $ S= $ `baaaaccccc` です。 - $ 5 $ 番目のクエリはタイプ $ 2 $ で、 $ l=1,r=10 $ です。 - 抜き出した文字列は `baaaaccccc` であり、 $ f( $ `baaaaccccc` $ )=5 $ です。 ### Sample Explanation 2 出力が空である場合もあります。 ### Constraints - $ N $ は $ 1 $ 以上 $ 5 \times 10^5 $ 以下の整数 - $ S $ は英小文字からなる長さ $ N $ の文字列 - $ Q $ は $ 1 $ 以上 $ 5 \times 10^5 $ 以下の整数 - タイプ $ 1 $ のクエリは以下の制約を満たす - $ i $ は $ 1 $ 以上 $ N $ 以下の整数 - $ x $ は英小文字 - タイプ $ 2 $ のクエリは以下の制約を満たす - $ l,r $ は $ 1 \le l \le r \le N $ を満たす整数