AT_joi2026_semifinal_f 奇妙な機械 (Strange Machine)

あなたはタイル $ 1 $ からタイル $ N $ までの番号が付けられている $ N $ 枚のタイルを持っている．各タイルの表面の色と裏面の色は黒色または白色である．ここで，黒色は文字 `B` で表し，白色は文字 `W` で表すことにする． タイル $ i $ ( $ 1 \leqq i \leqq N $ ) の表面の色は，文字列 $ S $ の $ i $ 文字目で表される色である． タイル $ i $ ( $ 1 \leqq i \leqq N $ ) の裏面の色は，文字列 $ T $ の $ i $ 文字目で表される色である． ウズベキスタンはタイル装飾による歴史的建築で有名な国である．ウズベキスタンのモスクやマドラサを訪れたあなたはそれらの美しい建築に魅了され，タイルに関する奇妙な機械を購入した．この機械は左側と右側に台を持ち，それぞれの台に $ 1 $ 枚ずつタイルを置くことで，置いた $ 2 $ 枚のタイルと引き換えに新しいタイルを $ 1 $ 枚受け取ることができる． 左側の台に置いたタイルを $ a $ ，右側の台に置いたタイルを $ b $ としたとき， $ 2 $ 枚のタイル $ a, b $ と引き換えに受け取ることができる新しいタイル $ c $ は以下の条件を満たす． - $ c $ の表面の色は， $ a $ の裏面の色と $ b $ の表面の色が同じとき黒色であり，そうでないとき白色である． - $ c $ の裏面の色は， $ a $ の表面の色と $ b $ の裏面の色が同じとき黒色であり，そうでないとき白色である． あなたは $ N $ 枚のタイルと奇妙な機械を用いて， $ Q $ 日間にわたり次のような行動を行うことにした． $ j $ 日目 ( $ 1 \leqq j \leqq Q $ ) に行う行動は以下のパターン $ 1 $ かパターン $ 2 $ のいずれかである． - パターン $ 1 $ ：タイル $ X_j $ の表面の色を文字 $ Y_j $ で表される色に変更する．また，タイル $ X_j $ の裏面の色を文字 $ Z_j $ で表される色に変更する．ただし， $ Y_j, Z_j $ は `B`, `W` のいずれかである． - パターン $ 2 $ ：タイル $ L_j, L_j + 1, \dots, R_j $ をこの順に左から右へ一列に並べる．この列に対して，以下の操作を $ 0 $ 回以上 $ R_j - L_j $ 回以下の好きな回数行うことで，列の中で表面が白色であるタイルをちょうど $ M_j $ 枚にできるかを判定する思考実験を行う． - 列の中で隣り合う $ 2 $ 枚のタイルを選んでそれらを列から取り除く．選んだ $ 2 $ 枚のタイルのうち，列において左側に置かれていたタイルを機械の左側の台に置き，右側に置かれていたタイルを機械の右側の台に置くことで，置いた $ 2 $ 枚のタイルと引き換えに新しいタイルを受け取る．そして，列の中で元々 $ 2 $ 枚のタイルがあった場所に，受け取った $ 1 $ 枚のタイルを入れる． タイルの情報と行動の情報が与えられたとき，パターン $ 2 $ の行動の結果を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ S $ $ T $ $ Q $ $ (\text{Query }1) $ $ (\text{Query }2) $ $ \vdots $ $ (\text{Query }Q) $ 各 $ (\text{Query }j) $ ( $ 1 \leqq j \leqq Q $ ) にはいくつかの整数や文字が空白区切りで書かれている．そのうち最初に書かれているものは整数 $ 1, 2 $ のいずれかであり，これを $ P_j $ とすると，この行の内容は以下のいずれかである． - $ P_j = 1 $ のとき，この行には続いて $ 1 $ 個の整数 $ X_j $ と $ 2 $ 個の文字 $ Y_j, Z_j $ がこの順に書かれている．これはあなたが $ j $ 日目に取る行動がパターン $ 1 $ であり，タイル $ X_j $ の表面の色を文字 $ Y_j $ で表される色に変更し，タイル $ X_j $ の裏面の色を文字 $ Z_j $ で表される色に変更することを表す．ただし， $ Y_j, Z_j $ は `B`, `W` のいずれかである． - $ P_j = 2 $ のとき，この行には続いて $ 3 $ 個の整数 $ L_j, R_j, M_j $ がこの順に書かれている．これはあなたが $ j $ 日目に取る行動がパターン $ 2 $ であり，タイル $ L_j, L_j + 1, \dots, R_j $ をこの順に左から右へ一列に並べ，この列に対して操作を行い，列の中で表面が白色であるタイルをちょうど $ M_j $ 枚にすることができるかを判定する思考実験を行うことを表す．

$ P_j = 2 $ となる $ j $ ( $ 1 \leqq j \leqq Q $ ) それぞれに対して，列の中で表面が白色であるタイルをちょうど $ M_j $ 枚にすることができるとき `Yes` を，そうでないとき `No` を， $ j $ の昇順に改行区切りで出力せよ． ---

### 小課題 1. ( $ 6 $ 点) $ N \leqq 6 $ ． 2. ( $ 10 $ 点) $ N \leqq 100 $ ， $ P_j = 2 $ ( $ 1 \leqq j \leqq Q $ )． 3. ( $ 9 $ 点) $ N \leqq 500 $ ， $ P_j = 2 $ ( $ 1 \leqq j \leqq Q $ )． 4. ( $ 8 $ 点) $ N \leqq 1\,700 $ ， $ P_j = 2 $ ( $ 1 \leqq j \leqq Q $ )． 5. ( $ 23 $ 点) $ N \leqq 10\,000 $ ， $ Q \leqq 10\,000 $ ． 6. ( $ 14 $ 点) $ N \leqq 100\,000 $ ， $ Q \leqq 100\,000 $ ． 7. ( $ 30 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 1 $ 日目の行動について，タイル $ 3, 4 $ をこの順に左から右へ一列に並べる．操作を $ 1 $ 回も行わない場合，タイル $ 3 $ のみ表面が白色であるため，列の中で表面が白色であるタイルをちょうど $ 1 $ 枚にすることができる．したがって，`Yes` を出力する． $ 2 $ 日目の行動について，タイル $ 1, 2 $ をこの順に左から右へ一列に並べる．タイル $ 1 $ とタイル $ 2 $ を選んで操作を $ 1 $ 回行う場合，操作した後の列は $ 1 $ 枚のタイルを含む．このタイルの表面と裏面は共に黒色であるため，列の中で表面が白色であるタイルをちょうど $ 0 $ 枚にすることができる．したがって，`Yes` を出力する． $ 3 $ 日目の行動について，タイル $ 3 $ の表面の色と裏面の色を共に黒色に変更する． $ 4 $ 日目の行動について，タイル $ 3, 4 $ をこの順に左から右へ一列に並べる．操作によって，列の中で表面が白色であるタイルをちょうど $ 2 $ 枚にすることはできないことが証明できる．したがって，`No` を出力する． $ 5 $ 日目の行動について，タイル $ 2, 3, 4 $ をこの順に左から右へ一列に並べる．タイル $ 3 $ とタイル $ 4 $ を選んで操作を $ 1 $ 回行う場合，操作した後の列は $ 2 $ 枚のタイルを含む．左側にあるタイルはタイル $ 2 $ であり，右側にあるタイルの表面と裏面は共に黒色である．この $ 2 $ 枚のタイルを選んでさらに操作を $ 1 $ 回行う場合，操作した後の列は $ 1 $ 枚のタイルを含む．このタイルの表面は白色で，裏面は黒色であるため，列の中で表面が白色であるタイルをちょうど $ 1 $ 枚にすることができる．したがって，`Yes` を出力する． この入力例は小課題 $ 1,5,6,7 $ の制約を満たす． --- ### Sample Explanation 2 この入力例はすべての小課題の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 300\,000 $ ． - $ S $ は `B`, `W` からなる長さ $ N $ の文字列である． - $ T $ は `B`, `W` からなる長さ $ N $ の文字列である． - $ 1 \leqq Q \leqq 300\,000 $ ． - $ P_j $ は $ 1,2 $ のいずれかである ( $ 1 \leqq j \leqq Q $ )． - $ P_j = 1 $ のとき， $ 1 \leqq X_j \leqq N $ ( $ 1 \leqq j \leqq Q $ )． - $ P_j = 1 $ のとき， $ Y_j $ は `B`, `W` のいずれかである ( $ 1 \leqq j \leqq Q $ )． - $ P_j = 1 $ のとき， $ Z_j $ は `B`, `W` のいずれかである ( $ 1 \leqq j \leqq Q $ )． - $ P_j = 2 $ のとき， $ 1 \leqq L_j \leqq R_j \leqq N $ ( $ 1 \leqq j \leqq Q $ )． - $ P_j = 2 $ のとき， $ 0 \leqq M_j \leqq R_j - L_j + 1 $ ( $ 1 \leqq j \leqq Q $ )． - $ N, Q, P_j, X_j, L_j, R_j, M_j $ はすべて整数である．