009 - All you need is Segment Tree.

問題

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 \ $を出力します。