JOI 2025/2026 セミファイナルステージ過去問

ログインしてください。

A - 座席 3 (Seats 3)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

2N+2 個の座席が横一列に並んでいる．左から i 番目の座席 (1 \leqq i \leqq 2N+2) の座り心地は A_i である．

2 人組で訪れたグループ客が N 組と，単身で訪れた VIP 客 2 人がおり，これら 2N+2 人の客に 1 人 1 個の座席を割り当てる．ただし，2 人以上の客に同じ座席を割り当ててはいけない．

いま，同じグループに属する 2 人には隣り合う座席を割り当てる必要がある．このとき，VIP 客 2 人に割り当てる 2 個の座席の座り心地の合計をなるべく大きくしたい．

座席の情報が与えられたとき，VIP 客 2 人に割り当てる 2 個の座席の座り心地の合計の最大値を求めるプログラムを作成せよ．

入力

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

N
A_1 A_2 \cdots A_{2N+2}

出力

標準出力に，VIP 客 2 人に割り当てる 2 個の座席の座り心地の合計の最大値を 1 行で出力せよ．

制約

1 \leqq N \leqq 200\,000．
1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq 2N+2)．
入力される値はすべて整数である．

小課題

(10 点) N = 1．
(10 点) N \leqq 2．
(10 点) N \leqq 3．
(30 点) N \leqq 2\,000．
(40 点) 追加の制約はない．

入力例 1

2
20 60 40 30 10 50

出力例 1

以下のように割り当てることで，VIP 客 2 人の座席の座り心地の合計は 90 になる．

1 組目のグループには左から 1, 2 番目の座席を割り当てる．
2 組目のグループには左から 4, 5 番目の座席を割り当てる．
VIP 客 2 人には左から 3, 6 番目の座席を割り当てる．

VIP 客 2 人の座席の座り心地の合計を 90 より大きくすることはできないので，90 を出力する．

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 2

1
1000000000 1000000000 1 1

出力例 2

2000000000

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

入力例 3

4
4 10 8 6 7 6 7 8 12 3

出力例 3

この入力例は小課題 4,5 の制約を満たす．

B - 宝石商 (Jeweler)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

JOI 君は宝石店を経営している．宝石店には宝石を買おうとしている客が N 人おり，これらの客には 1 から N までの番号が付けられている．客 i (1 \leqq i \leqq N) は時刻 L_i から時刻 R_i までの間の任意の時刻に店を訪れることができ，宝石を C_i 個購入しようとしている．

JOI 君は忙しいため，常に店を開けておくことができない．そこで，店を開ける時間について M 個の案を考えた．案には 1 から M までの番号が付けられており，案 j (1 \leqq j \leqq M) は，時刻 S_j - 0.1 から時刻 T_j + 0.1 までの間店を開けるというものである．それぞれの案について，客 i (1 \leqq i \leqq N) は，自分が訪れることができる時間帯に店が開いている時刻があれば，店を訪れ宝石を C_i 個購入する．逆にそうではない場合，客 i は店を訪れず，宝石を購入しない．ただし，JOI 君の店には十分な数の宝石があり，宝石が売り切れることはないものとする．

JOI 君の店の客の情報と店を開けておく時間の案が与えられたとき，それぞれの案について，宝石が合計でいくつ売れるかを求めるプログラムを作成せよ．

入力

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

N
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_N R_N C_N
M
S_1 T_1
S_2 T_2
\vdots
S_M T_M

出力

標準出力に M 行出力せよ．j 行目 (1 \leqq j \leqq M) には，案 j において宝石が合計でいくつ売れるかを出力せよ．

制約

1 \leqq N \leqq 300\,000．
1 \leqq L_i < R_i \leqq 1\,000\,000 (1 \leqq i \leqq N)．
1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N)．
1 \leqq M \leqq 300\,000．
1 \leqq S_j \leqq T_j \leqq 1\,000\,000 (1 \leqq j \leqq M)．
入力される値はすべて整数である．

小課題

(12 点) N \leqq 1\,000，M \leqq 1\,000．
(17 点) S_j = T_j (1 \leqq j \leqq M)．
(21 点) S_j = 1 (1 \leqq j \leqq M)．
(23 点) S_j \leqq S_{j+1}，T_j \leqq T_{j+1} (1 \leqq j < M)．
(27 点) 追加の制約はない．

入力例 1

出力例 1

60
0
50

案 1 では，時刻 3.9 から時刻 6.1 まで店を開ける．客 1 は時刻 4 に，客 2 は時刻 5 に，客 3 は時刻 6 に店で宝石を買うことができ，宝石は合計で 10 + 20 + 30 = 60 個売れる．

案 2 では，時刻 0.9 から時刻 2.1 まで店を開ける．どの客も店が開いている時刻に訪れることができないため，宝石は合計で 0 個売れる．

案 3 では，時刻 5.9 から時刻 8.1 まで店を開ける．客 2，客 3 ともに時刻 7 に店で宝石を買うことができ，宝石は合計で 20 + 30 = 50 個売れる．

この入力例は小課題 1,5 の制約を満たす．

入力例 2

出力例 2

5
7
15

案 1 では，客 1 と客 3 が店で宝石を買うことができ，宝石は合計で 1 + 4 = 5 個売れる．案 2 では，客 1，客 2，客 3 が店で宝石を買うことができ，宝石は合計で 1 + 2 + 4 = 7 個売れる．案 3 では，すべての客が店で宝石を買うことができ，宝石は合計で 1 + 2 + 4 + 8 = 15 個売れる．

この入力例は小課題 1,3,4,5 の制約を満たす．

入力例 3

10
55 882 861052753
104 734 331227764
492 694 240198464
481 506 377367203
131 185 327968773
124 129 970226535
92 125 133053911
356 442 758055457
21 759 730522637
259 481 948997757
9
50 287
510 735
158 431
113 768
328 894
783 881
163 692
42 862
43 752

出力例 3

この入力例は小課題 1,5 の制約を満たす．

C - 衣服 (Clothes)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

ビーバーのビ太郎は，これから服屋で 0 枚以上の服を購入しようとしている．服屋では全部で 100 種類の服が販売されており，服の種類には 1 から 100 までの番号が付けられている．服屋にはそれぞれの種類の服の在庫が十分な数用意されており，ビ太郎がいくら服を買っても品切れになることはない．

ビ太郎は，購入した服を着ることで体感温度を調節することができる．気温が t 度であり，ビ太郎が種類 s_1, s_2, \ldots, s_k の k 枚の服を着ている場合，ビ太郎の体感温度は t + s_1 + s_2 + \cdots + s_k 度である．ただし，ビ太郎は 0 枚以上の好きな枚数の服を着ることができる (服を着ていない，すなわち k = 0 の場合は体感温度は t 度である)．また，ビ太郎は同じ種類の服を一度に複数枚着ることもでき，その種類の服を着た分だけ体感温度は重複して上昇することに注意せよ．

ビ太郎は天気予報により，今後 N 日間の気温は順に A_1 度，A_2 度，\ldots，A_N 度になることを知った．ビ太郎は服屋で適切に服を購入することで，今後 N 日間のいずれの日も，うまく着る服を選ぶことで体感温度を 23 度にできるようにしたいと考えている．また，そのような服の購入が可能である場合は，購入する服の枚数を最小限にしたいと考えている．

今後 N 日の気温の情報が与えられたとき，ビ太郎がいずれの日も体感温度を 23 度にできるような服の購入は可能であるか判定し，可能である場合は購入する服の数が最小となるような服の買い方の一例を求めるプログラムを作成せよ．

入力

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

N
A_1 A_2 \cdots A_N

出力

標準出力に以下の形式で出力せよ．

ビ太郎がいずれの日も体感温度を 23 度にできるような服の購入が不可能である場合，No と出力せよ．

ビ太郎がいずれの日も体感温度を 23 度にできるような服の購入が可能である場合，1 行目に Yes と出力せよ．さらに，ビ太郎が購入する服の数の最小値を k とし，購入する k 枚の服の種類をそれぞれ s_1, s_2, \ldots, s_k として， 2 行目に k を出力し，3 行目に k 個の整数 s_1, s_2, \ldots, s_k を空白区切りで出力せよ． k 個の整数 s_1, s_2, \ldots, s_k はどの順番で出力してもよい．また，条件を満たす服の購入の仕方が複数存在する場合，そのうちどれを出力してもよい．

制約

1 \leqq N \leqq 81．
-40 \leqq A_i \leqq 40 (1 \leqq i \leqq N)．
A_i < A_{i + 1} (1 \leqq i \leqq N - 1)．
入力される値はすべて整数である．

小課題

(6 点) N = 1．
(14 点) N \leqq 3．
(15 点) A_{i + 1} = A_i + 1 (1 \leqq i \leqq N - 1)，A_N = 23．
(16 点) A_i \geqq 12 (1 \leqq i \leqq N)．
(9 点) A_i \geqq 4 (1 \leqq i \leqq N)．
(21 点) A_i \geqq -8 (1 \leqq i \leqq N)．
(19 点) 追加の制約はない．

入力例 1

3
17 20 23

出力例 1

Yes
2
3 3

ビ太郎は種類 3 の服を 2 枚購入することで，今後 3 日間のいずれの日も体感温度を 23 度となるようにすることができる．具体的には，以下のように服を着ることでいずれの日も体感温度が 23 度となるようにすることができる．

1 日目は，種類 3 の服を 2 枚着る．
2 日目は，種類 3 の服を 1 枚着る．
3 日目は，服を 1 枚も着ない．

1 枚以下の服の購入で今後 3 日間のいずれの日も体感温度が 23 度となるようにすることはできない．

この入力例は小課題 2, 4, 5, 6, 7 の制約を満たす．

入力例 2

1
24

出力例 2

No

気温が 24 度の日は体感温度を 23 度となるようにすることができない．したがって，どのように服を購入しても，今後 1 日間のいずれの日も体感温度が 23 度となるようにすることはできない．

この入力例は小課題 1, 2, 4, 5, 6, 7 の制約を満たす．

入力例 3

5
-1 3 6 10 16

出力例 3

Yes
3
4 7 13

この入力例は小課題 6, 7 の制約を満たす．

入力例 4

3
21 22 23

出力例 4

Yes
2
1 1

この入力例は小課題 2, 3, 4, 5, 6, 7 の制約を満たす．

D - 川下り(River Rafting)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

JOI 国には N 個の街があり，街には 1 から N までの番号が付けられている．これらの街の間には N-1 本の道があり，1 から N - 1までの番号が付けられている．道 i (1 \leqq i \leqq N-1) は街 P_i (P_i \leqq i) と街 i + 1 とを相互に結んでいる．街 1 からどの街へも何本かの道を通って移動できることが保証されている．また，JOI 国には道に並行する川が N - 1 本あり，川には 1 から N - 1 までの番号が付けられている．川 i (1 \leqq i \leqq N-1) は道 i と並行しており，街 P_i から街 i + 1 の向きに流れている．

N 個の街にはそれぞれ 1 つずつランプが置いてある．各ランプには強さが定められている．街 t (1 \leqq t \leqq N) にあるランプの強さが l であるとき，その街から l 本未満の道を通って到達できる街はこのランプによって照らされている．最初の時点では，ランプの強さはすべて 0 であり，どの街も照らされていない．

あなたは川下りを 0 回以上の好きな回数行うことが出来る．川下りは街 1 にいる状態から始めて，まず街 1 にあるランプの強さを 1 増やす．そして，以下の操作を順に繰り返す．

川下りを終了するか決める．ただし今いる街から流れる川が存在しないときは必ず終了する．
川下りを続ける場合，今いる街から流れる川を 1 つ選び，その川の流れに沿って移動する．移動した先の街のランプの強さを 1 増やす．

川下りを街 t で終了した場合，この川下りにかかるコストは C_t である．あなたは，川下りを 0 回以上の好きな回数行うことで，すべての街がいずれかのランプによって照らされるようにしたい．その上で，川下りにかかるコストの合計を最小化する必要がある．

道とコストの情報が与えられたとき，すべての街がいずれかのランプによって照らされるようにするための川下りにかかるコストの合計の最小値を求めるプログラムを作成せよ．

入力

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

N
P_1 P_2 \cdots P_{N-1}
C_1 C_2 \cdots C_N

出力

標準出力に，すべての街がいずれかのランプによって照らされるようにするための川下りにかかるコストの合計の最小値を 1 行で出力せよ．

制約

2 \leqq N \leqq 700．
1 \leqq P_i \leqq i (1 \leqq i \leqq N-1)．
1 \leqq C_t \leqq 10^9 (1 \leqq t \leqq N)．
入力される値はすべて整数である．

小課題

(13 点) N \leqq 8．
(25 点) N \leqq 100．
(7 点) P_i = 1 (1 \leqq i \leqq N-1)．
(11 点) P_i = i (1 \leqq i \leqq N-1)．
(16 点) すべての i (1 \leqq i \leqq N) に対して，P_j = i となる j (1 \leqq j \leqq N-1) は 2 個以下．
(28 点) 追加の制約はない．

入力例 1

5
1 2 2 4
10 4 8 9 5

出力例 1

1 回目の川下りでは川 1 を選択し，街 2 で川下りを終了する．このとき街 1, 2 にあるランプの強さが 1 増え，コストは 4 である． 2 回目の川下りでは川 1, 3, 4 を選択し，街 5 で川下りを終了する．このとき街 1, 2, 4, 5 にあるランプの強さが 1 増え，コストは 5 である．

操作の後，街 1, 2 にあるランプの強さは 2，街 3 にあるランプの強さは 0，街 4, 5 にあるランプの強さは 1 となる．街 1, 2, 3, 4 は街 2 にある強さ 2 のランプによって，街 5 は街 5 にある強さ 1 のランプによって照らされる．したがって，これらの操作によりすべての街はいずれかのランプによって照らされる．このときコストの合計は 4 + 5 = 9 である． 9 未満のコストで条件を満たすことはできないため，9 を出力する．

この入力例は小課題 1, 2, 5, 6 の制約を満たす．

入力例 2

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

出力例 2

川 1, 4, 5 を通って街 6 で終了する川下りを 2 回，川 2, 8 を通って街 9 で終了する川下りを 1 回行う．操作の後，街 1 にあるランプの強さは 3，街 2, 5, 6 にあるランプの強さは 2，街 3, 9 にあるランプの強さは 1，街 4, 7, 8 にあるランプの強さは 0 となる．これらの操作によりすべての街はいずれかのランプによって照らされる．このときコストの合計は 30 \times 2 + 30 = 90 である．90 未満のコストで条件を満たすことはできないため，90 を出力する．

この入力例は小課題 2, 6 の制約を満たす．

E - 新たな橋 (New Bridge)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

JOI 国は N 個の島からなる国であり，各島には 1 から N までの番号が付けられている．現在，この国には島と島の間を結ぶ橋が存在しておらず，住民は不便な生活を送っている．

そこで，JOI 国の大臣であるあなたは国家事業として新たに橋を架けることにした．橋を架ける建設計画が M 個あり，j 番目 (1 \leqq j \leqq M) の建設計画は，費用 C_j をかけて，島 A_j と島 B_j の間を双方向に結ぶ橋を架けるものである．ここで，C_1, C_2, \ldots, C_M は相異なることが保証される．また，すべての建設計画を実行した場合において，すべての島がいくつかの橋によって互いに到達可能になることが保証される．

JOI 国の予算は限られているので，あなたは，次のように国家事業を実施することに決めた．

N 個の島の中からひとつの島 s を選び，その島を首都とする．
以下の操作を N - 1 回行う．
- 各操作をする前の時点で，いくつかの橋を用いて首都から到達可能である島を近い島，そうでない島を遠い島とする．架ける橋の一端が近い島，もう一端が遠い島であるような建設計画のうち，費用が最も安いものを選び，実行する．
操作を N - 1 回行った後，国家事業を終了する．

ここで，建設計画の満たす制約より，以下の事柄を証明できる．

各操作において，選ぶことのできる建設計画は必ず存在する．さらに，実行される建設計画は一意に定まる．
この事業が終了した時点で，すべての島がいくつかの橋によって互いに到達可能になる．

JOI 国への移住を検討している凛は，どの島に住むかの参考にするため，次のように各島の不便度を計算することにした．島 i (1 \leqq i \leqq N) の不便度は次のように定義される．

島 s (1 \leqq s \leqq N) を首都として国家事業を実施したときに，島 i が首都から到達可能になるまでに実行された建設計画の数を D_{s, i} とする．ここで，s = i のときは D_{s, i} は 0 とする．
島 i の不便度は，すべての 1 \leqq s \leqq N に対する D_{s, i} の総和とする．

凛は，引っ越し先の候補としている Q 個の島 X_1, X_2, \ldots, X_Q の不便度を計算したい．建設計画と引っ越し先の候補の島の情報が与えられたとき，これらの島の不便度を求めるプログラムを作成せよ．

入力

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

N M Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
X_1
X_2
\vdots
X_Q

出力

Q 行出力せよ．k 行目には，島 X_k (1 \leqq k \leqq Q) の不便度を出力せよ．

制約

2 \leqq N \leqq 300\,000．
1 \leqq M \leqq 600\,000．
1 \leqq Q \leqq N．
1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq M)．
すべての建設計画を実行した場合において，すべての島がいくつかの橋によって互いに到達可能になる．
1 \leqq C_j \leqq 10^9 (1 \leqq j \leqq M)．
C_1, C_2,\ldots,C_M は相異なる．
1 \leqq X_k\leqq N (1 \leqq k \leqq Q)．
X_1, X_2, \ldots, X_Q は相異なる．
入力される値はすべて整数である．

小課題

(5 点) N \leqq 2\,000，M \leqq 2\,000．
(8 点) N \leqq 2\,000．
(9 点) M = N - 1，A_j = j, B_j = j + 1 (1 \leqq j \leqq M)，Q = 1．
(18 点) M = N - 1，A_j = j, B_j = j + 1 (1 \leqq j \leqq M)．
(28 点) Q = 1．
(32 点) 追加の制約はない．

入力例 1

出力例 1

7
3

例えば，島 1 を首都として，国家事業を実施した場合を考える．このとき，次のように建設計画が実行される．

1 番目の建設計画が実行される．首都からは新たに島 3 が到達可能になる．
3 番目の建設計画が実行される．首都からは新たに島 2 が到達可能になる．
5 番目の建設計画が実行される．首都からは新たに島 4 が到達可能になる．

以上より，D_{1, 1} = 0, D_{1, 2} = 2, D_{1, 3} = 1, D_{1, 4} = 3 となる．

D_{2, 1} = 2, D_{3, 1} = 2, D_{4, 1} = 3 であるため，島 1 の不便度は D_{1, 1} + D_{2, 1} + D_{3, 1} + D_{4, 1} = 0 + 2 + 2 + 3 = 7 である．また，D_{2, 3} = 1, D_{3, 3} = 0, D_{4, 3} = 1 であるため，島 3 の不便度は D_{1, 3} + D_{2, 3} + D_{3, 3} + D_{4, 3} = 1 + 1 + 0 + 1 = 3 である．

この入力例は小課題 1, 2, 6 の制約を満たす．

入力例 2

出力例 2

この入力例は小課題 1, 2, 4, 6 の制約を満たす．

入力例 3

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

出力例 3

この入力例は小課題 1, 2, 5, 6 の制約を満たす．

F - 奇妙な機械 (Strange Machine)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点： 100 点

問題文

あなたはタイル 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 \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 はすべて整数である．

小課題

(6 点) N \leqq 6．
(10 点) N \leqq 100，P_j = 2 (1 \leqq j \leqq Q)．
(9 点) N \leqq 500，P_j = 2 (1 \leqq j \leqq Q)．
(8 点) N \leqq 1\,700，P_j = 2 (1 \leqq j \leqq Q)．
(23 点) N \leqq 10\,000，Q \leqq 10\,000．
(14 点) N \leqq 100\,000，Q \leqq 100\,000．
(30 点) 追加の制約はない．

入力例 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

出力例 2

No
Yes
Yes
Yes
Yes
No
No
Yes

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