AT_KeioPC2025_r Many Strings

長さ $ N $ の文字列 $ S $ が与えられます。また、空文字列で初期化された $ 2\times10^5 $ 個の文字列 $ T_1, T_2, \ldots , T_{200000} $ があります。 以下の形式で与えられる $ Q $ 個のクエリを、与えられた順番に処理してください。 クエリは次の $ 2 $ 種類のいずれかです。 - タイプ1: `1 k l r` の形式で与えられる。 $ T_k $ を $ T_k $ と $ S $ の $ l $ 文字目から $ r $ 文字目までからなる部分文字列をその順に連結したもので置き換える。 - タイプ2: `2 x y` の形式で与えられる。 $ T_x $ の方が $ T_y $ よりも辞書順で大きい場合は `>` を、小さい場合は `

入力は以下の形式で標準入力から与えられる。 > $ N\ Q $ $ S $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは次の形式のいずれかで与えられる。 > $ 1\ k\ l\ r $ > $ 2\ x\ y $

タイプ $ 2 $ のクエリの回数を $ q $ 回として $ q $ 行出力せよ。 $ j $ 行目には、タイプ $ 2 $ のクエリのうち $ j $ 個目のものに対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のクエリ : $ T_1 $ を $ T_1 $ と `keio` を連結したもので置き換えます。置き換え後の $ T_1 $ は `keio` になります。 - $ 2 $ 番目のクエリ : $ T_2 $ を $ T_2 $ と `procon` を連結したもので置き換えます。、置き換え後の $ T_2 $ は `procon` になります。 - $ 3 $ 番目のクエリ : $ T_1 $ と $ T_2 $ を比較します。 $ T_1 = $ `keio` , $ T_2 = $ `procon` であり、辞書順で比較すると $ T_1 $ の方が小さいため `` を出力します。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ S $ は英小文字からなる長さ $ N $ の文字列 - $ 1 \leq k \leq 2 \times 10^5 $ - $ 1 \leq l \leq r \leq N $ - $ 1 \leq x,y \leq 2 \times 10^5 $ - $ x \neq y $ - $ N,Q,k,l,r,x,y $ は整数