問題
oとxのみからなる長さ$ \ N \ $の文字列$ \ S \ $与えられます。以下のようなクエリが$ \ Q \ $個与えられるので順に処理してください。
-
1 k:$S \ $の$ \ k \ $番目の文字がoならxに、xならoに書き換える。 -
2 l r:$S \ $の$ \ l \ $文字目から$ \ r \ $文字目までの文字列について、連続したoの個数の最大値を出力する。
入力
入力は以下の形式で標準入力から与えられる。
$N \ Q$ $S$ $Query_1$ $Query_2$ $\vdots$ $Query_Q$
各クエリは以下のいずれかの形式で与えられる。
$1 \ k$
$2 \ l \ r$
出力
出力クエリに対する答えを改行区切りで出力せよ。
制約
- $1 \leq N,Q \leq 2 \times 10^5$
- $S \ $は
oとxのみからなる長さ$ \ N \ $の文字列 - $1 \leq k \leq N$
- $1 \leq l \leq r \leq N$
入出力例
入力例
5 3 ooxox 2 1 3 1 3 2 2 5
出力例
2 3
- クエリ1: $S \ $の$ \ 1 \ $番目から$ \ 3 \ $番目までの文字列は
ooxです。連続したoの個数の最大値は、$1\ $文字目から$ \ 2 \ $文字目までの$ \ 2 \ $つなので$ \ 2 \ $を出力します。 - クエリ2: $S \ $の$ \ 3 \ $文字目は
xなのでoに書き換えられ$ \ S \ = $ooooxとなります。 - クエリ3: $S \ $の$ \ 2 \ $番目から$ \ 5 \ $番目までの文字列は
oooxです。連続したoの個数の最大値は、$1\ $文字目から$ \ 3 \ $文字目までの$ \ 3 \ $つなので$ \ 3 \ $を出力します。