006 - HOJ-Substrings

問題

レベル$ \ k \ $のHOJ文字列を、文字H,O,Jをこの順に$ \ k \ $個ずつ繋げた文字列と定義します。なお、レベル$ \ 0 \ $のHOJ文字列は空文字列です。

長さ$ \ N \ $の文字列$ \ S \ $と$ \ Q \ $個のクエリが与えられるので順に処理してください。

• クエリ1：1 p c：$S \ $の$ \ p \ $文字目を文字$ \ c \ $に変更する。
• クエリ2：2 l r：$S \ $の$ \ l \ $文字目から$ \ r \ $文字目までを$ \ S[l:r] \ $としたとき、$S[l:r] \ $の部分文字列であるようなHOJ文字列のレベルの最大値を出力する。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$S$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

各クエリは以下のいずれかの形式で与えられる。

$1 \ p \ c$

$2 \ l \ r$

出力

クエリ2についての答えを改行区切りで出力せよ。

制約

• $1 \leq N,Q \leq 3 \times 10^5$
• $S \ $はH,O,Jのみからなる長さ$ \ N \ $の文字列
• $1 \leq p \leq N$
• $c \in \{$H,O,J$\}$
• $1 \leq l \leq r \leq N$

入出力例

入力例

10 5
HOHOOJOJJJ
2 1 10
2 3 7
2 2 3
1 2 H
2 1 10

出力例

2
1
0
3

1. HOHOOJOJJJにはレベル$ \ 2 \ $のHOJ文字列HHOOJJが部分文字列として含まれます。
2. HOOJOにはレベル$ \ 1 \ $のHOJ文字列HOJが部分文字列として含まれます。
3. OHにはレベル$ \ 0 \ $のHOJ文字列である空文字列が部分文字列として含まれます。
4. $S \ $の$ \ 2 \ $文字目がHとなり$S = $HHHOOJOJJJとなります。
5. HHHOOJOJJJにはレベル$ \ 3 \ $のHOJ文字列HHHOOOJJJが部分文字列として含まれます。