問題文

あなたはタイル 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 の行動の結果を求めるプログラムを作成せよ．

制約

• 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 はすべて整数である．

小課題

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 点) 追加の制約はない．

入力例 1

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

出力例 1

Yes
Yes
No
Yes

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 の制約を満たす．

入力例 2

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

出力例 2

No
Yes
Yes
Yes
Yes
No
No
Yes

この入力例はすべての小課題の制約を満たす．