AT_pakencamp_2023_day3_h ROT

空でない文字列 $ X $ と非負整数 $ K $ に対して、 $ \operatorname{rot}(X,K) $ を次のように定めます。 - $ X $ の先頭の文字を末尾に移動させるという操作を $ K $ 回行った結果得られる文字列。 長さの等しい空でない文字列 $ X, Y $ に対し、 $ f(X, Y) $ を次のように定めます。 - $ 0\leq i\lt|X| $ かつ $ \operatorname{rot}(X,i) $ が $ \operatorname{rot}(Y,i) $ よりも辞書順で小さくなるような整数 $ i $ の個数。 正整数 $ N $ と、ともに長さが $ N $ である文字列 $ S,T $ が与えられます。以下の $ 2 $ 種類のクエリが合計で $ Q $ 個与えられるので処理してください。 - クエリ $ 1 $ : 整数 $ L,R $ が与えられる。 $ S $ の $ L $ 文字目から $ R $ 文字目までを抜き出して得られる文字列を $ S' $ 、 $ T $ の $ L $ 文字目から $ R $ 文字目までを抜き出して得られる文字列を $ T' $ として、 $ f(S',T') $ を求める。 - クエリ $ 2 $ : 整数 $ X, Y $ と英小文字 $ C $ が与えられる。 $ X = 1 $ のとき $ S $ の $ Y $ 文字目を $ C $ で置き換える。 $ X = 2 $ のとき $ T $ の $ Y $ 文字目を $ C $ で置き換える。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ S $ $ T $ $ Q $ $ \mathrm{Query}_{1} $ $ \mathrm{Query}_{2} $ $ \vdots $ $ \mathrm{Query}_{Q} $ ただし、 $ \mathrm{Query}_{i} $ は $ i $ 番目のクエリの内容を表します。それぞれのクエリの内容は以下の形式で与えられます。 - $ i $ 番目のクエリがクエリ $ 1 $ であるとき > $ 1 $ $ L $ $ R $ - $ i $ 番目のクエリがクエリ $ 2 $ であるとき > $ 2 $ $ X $ $ Y $ $ C $

それぞれのクエリ $ 1 $ について答えを $ 1 $ 行に出力してください。

### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 $ S'=\mathtt{acb},T'=\mathtt{cab} $ であり、 $ f(S',T') $ を出力する必要があります。 - $ \operatorname{rot}(S',0)=\mathtt{acb},\operatorname{rot}(T',0)=\mathtt{cab} $ - $ \operatorname{rot}(S',1)=\mathtt{cba},\operatorname{rot}(T',1)=\mathtt{abc} $ - $ \operatorname{rot}(S',2)=\mathtt{bac},\operatorname{rot}(T',2)=\mathtt{bca} $ ですから、このクエリに対する出力は $ 2 $ です。 ### Constraints - $ 1\leq N\leq 2\times 10^{5} $ - $ S $ と $ T $ は英小文字からなる長さ $ N $ の文字列 - $ 1\leq Q\leq 2\times 10^{5} $ - クエリ $ 1 $ について、 $ 1\leq L\leq R\leq N $ - クエリ $ 2 $ について、 $ X\in\lbrace 1,2\rbrace,1\leq Y\leq N $ であり、 $ C $ は英小文字