JOI 美術館では，近々絵の展覧会が開催される予定である． 美術館には 1 から N までの番号が付けられた N 枚の絵が所蔵されており，絵 i (1 \leqq i \leqq N) の 美しさ は A_i である． 展覧会ではこれらの絵を左から右に一列に並べて展示するが，並べる順番はまだ決まっていない．

展覧会には M 誌の雑誌が取材に来る予定である． これらの雑誌には発信力が高い順に 1 から M までの番号が付けられており，各雑誌は一列に並べられた絵のうちある区間に含まれる絵の写真を掲載する予定である． 具体的には，雑誌 j (1 \leqq j \leqq M) は左から L_j, L_j+1, \dots, R_j 番目に並べられた絵の写真を掲載する． ここで，雑誌 j (1 \leqq j \leqq M) の記事の 魅力度 は，雑誌 j が写真を掲載する絵の美しさの最大値として定義される．

JOI 美術館の館長である JOI 君は，絵の並べ方を工夫し，これらの雑誌により魅力度の高い記事を書いてもらうことで，より多くの人に展覧会への興味を持ってもらおうと考えている． ただし，発信力が高い雑誌ほどより多くの人の目にとまると考えられるので，発信力が高い雑誌に魅力度の高い記事を書いてもらうことを優先したい． より正確には，雑誌 j (1 \leqq j \leqq M) の記事の魅力度を b_j としたとき，JOI 君は数列 b=(b_1,b_2,\dots,b_M) が辞書順で最大となるように絵を並べる． ここで，相異なる数列 b=(b_1,b_2,\dots,b_M) および b'=(b'_1,b'_2,\dots,b'_M) に対して b が b' より 辞書順で大きい とは，b_k \neq b'_k であるような最小の k (1\leqq k\leqq M) に対して b_k > b'_k であることをいう．

展覧会で展示される絵および取材に来る雑誌の情報が与えられたとき，数列 b=(b_1,b_2,\dots,b_M) が辞書順で最大となるように絵を並べたときの各雑誌の記事の魅力度を求めるプログラムを作成せよ．

制約

• 1\leqq N\leqq 100\,000．
• 1\leqq M\leqq 100\,000．
• 1\leqq A_i\leqq N (1\leqq i\leqq N)．
• 1\leqq L_j\leqq R_j\leqq N (1\leqq j\leqq M)．
• 入力される値はすべて整数である．

小課題

1. (19 点) N ≦ 400，M ≦ 400．
2. (9 点) N ≦ 400．
3. (19 点) A_i\leqq 5 (1\leqq i\leqq N)．
4. (12 点) A_i=i (1\leqq i\leqq N)．
5. (17 点) 各 k (1\leqq k\leqq N) について，A_i=k を満たす i (1\leqq i\leqq N) の個数は高々 5 個である．
6. (24 点) 追加の制約はない．

入力例 1

4 4
1 2 1 2
1 1
2 3
4 4
3 4

出力例 1

2
2
1
2

左から絵 2,3,4,1 の順に並べたとき，各雑誌の記事の魅力度は以下のようになる．

• 雑誌 1：絵 2 の写真を掲載する．この絵の美しさは 2 であるため，記事の魅力度は 2 である．
• 雑誌 2：絵 3,4 の写真を掲載する．これらの絵の美しさはそれぞれ 1,2 であるため，記事の魅力度は 2 である．
• 雑誌 3：絵 1 の写真を掲載する．この絵の美しさは 1 であるため，記事の魅力度は 1 である．
• 雑誌 4：絵 4,1 の写真を掲載する．これらの絵の美しさはそれぞれ 2,1 であるため，記事の魅力度は 2 である．

このとき，数列 b は (2,2,1,2) となる．数列 b がこれより辞書順で大きくなるような絵の並べ方は存在しないため，2,2,1,2 をこの順に改行区切りで出力する．

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

入力例 2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

出力例 2

4
4
3
2
4
1
1
3

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

入力例 3

12 10
6 2 2 5 2 5 2 3 3 3 2 2
3 5
10 12
12 12
2 4
8 9
10 11
1 3
7 9
9 10
10 11

出力例 3

6
5
5
6
5
3
6
5
5
3

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

問題文

Anna と Bruno は占いが好きでいつも二人で様々な占いをしている．今日は 0 か 1 が書かれたカードを使って Q 回の占いを行うことにした．この占いは二人が協力して行う必要があり，1 回の占いを行う具体的な方法は次のようなものである．

1. 0 か 1 が書かれたカードをたくさん用意し，シャッフルして山札にする．
2. Anna は山札からカードを 1 枚ずつ，合計 N (=900) 枚引く．ここで，Anna と Bruno は N の値を知っている．Anna はカードを 1 枚引く度にそのカードを捨てるか，場に出して並べるかを選択する．
   • 場に出して並べることを選択した場合は，すでに場に並べてあるカードの列の好きな位置に，今回並べるカードを挿入して並べる．
   • 具体的には，すでに場に l 枚のカードが並べてある場合，非負整数 x (0 \leqq x \leqq l) を指定して，場に並べてあるカードの列の左から x 枚目のカードのすぐ右に挿入することができる．ただし x=0 のときはカードの列の一番左に挿入するとする．
3. Anna が N 枚のカードを引き終わると，Anna の役割は終了である．引いた N 枚のカードのうち 1 の書かれたカードの枚数が占いの結果である．
4. Bruno は最後に場に並べてあるカードの列のみを見て，占いの結果を推測する．Bruno が占いの結果を正しく答えることができれば占いは成功である．

この占いにおいては，場に出すカードの枚数が少ないほど上手な占いであるとされる．Anna と Bruno が Q 回の占いを成功させるための戦略を実装したプログラムを作成せよ．この課題では，Anna が場に出すカードの枚数が少ないほど，あなたは高得点を得る．

実装の詳細

あなたは 2 つのファイルを提出しなければならない．

1 つ目のファイルは Anna.cpp という名前である．このファイルは Anna の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Anna.h を読み込むこと．

• void Anna(int N)
  この関数は，合計 Q 回呼び出される．i 回目 (1 \leqq i \leqq Q) の呼び出しは，i 回目の占いにおける Anna の手順に相当する．
• 引数 N は，Anna が山札からカードを引く枚数 N である．

関数 Anna の 1 回の呼び出しについて，以下の関数を N+1 回呼び出さなければならない．

• int DrawCard(int x)
  この関数を用いて，山札からカードを引き，そのカードを捨てるか，場に出して並べるかを選択する．j 回目 (1 \leqq j \leqq N) の呼び出しの戻り値で，j 枚目に引いたカードに書かれた数を受け取る．k 回目 (2 \leqq k \leqq N+1) の呼び出しの引数で k-1 枚目に引いたカードに対する操作を指定する．
  • j 回目 (1\leqq j \leqq N) の呼び出しにおける戻り値は 0 または 1 であり，Annaが j 枚目に引いたカードに書かれた数を表す．
  • N+1 回目の呼び出しにおける戻り値は -1 であり，Annaが N 枚のカードを引き終えたことを表す．
  • 1 回目の呼び出しにおける引数 x は x=-1 を満たさなければならない．これが満たされない場合 不正解 [1] と判定される．
  • k 回目 (2\leqq k \leqq N+1) の呼び出しにおける引数 x は k-1 枚目に引いたカードに対する操作を指定する．x=-1 のとき，k-1 枚目に引いたカードを捨てることを表す．0\leqq xのとき，k-1 枚目に引いたカードをすでに場にあるカードの列の左から x 枚目のカードのすぐ右に挿入することを表す．ただし x=0 のときはカードの列の一番左に挿入することを表す．ここで，すでに場にあるカードの枚数を l として -1 \leqq x \leqq l を満たさなければならない．これが満たされない場合，不正解 [2] と判定される．
  • 関数 Anna の実行の終了時に関数 DrawCard の呼び出し回数が N+1 回でなかった場合，不正解 [3] と判定される．

2 つ目のファイルは Bruno.cpp という名前である． このファイルは Bruno の戦略を実装したファイルであり，以下の関数を実装していなければならない． また，#include プリプロセッサ指令によって Bruno.h を読み込むこと．

• int Bruno(int N, int L, std::vector<int> C)
  この関数は，Anna が一連の占いの手順を終える度に 1 回，合計で Q 回呼び出される．i 回目 (1 \leqq i \leqq Q) の呼び出しは，i 回目の占いにおける Bruno の手順に相当する．Anna が山札から引いた 1 の書かれたカードの枚数を戻り値として返さなければならない．
  • 引数 N は Anna が山札からカードを引いた枚数 N である．
  • 引数 L は場に並べられたカードの枚数 L である．
  • 引数 C は，長さ L の配列であり，C[l-1] は場の左から l 番目 (1 \leqq l \leqq L) に並べられたカードに書かれた数を表す．
  • 関数 Bruno の戻り値が Anna が山札から引いた 1 の書かれたカードの枚数と異なる場合，不正解 [4] と判定される．

重要な注意

• 内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．ただし，提出された 2 つのプログラムは，採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので，各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して，他のファイルとの干渉を避ける必要がある．採点時には，このプログラムは Anna 側，Bruno 側として 2 個のプロセスとして実行されるので，Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない．
• あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

作成したプログラムをテストするための，採点プログラムのサンプルが，コンテストサイトからダウンロードできるアーカイブの中に含まれている．このアーカイブには，提出しなければならないファイルのサンプルも含まれている．

採点プログラムのサンプルは 1 つのファイルからなる．そのファイルは grader.cpp である．作成したプログラムをテストするには，grader.cpp，Anna.cpp，Bruno.cpp，Anna.h，Bruno.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること．採点プログラムのサンプルは単一のプロセスとして起動する．このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

採点に関する注意

すべてのテストケースについて，実際の採点プログラムは適応的 (adaptive) ではない．これは，採点プログラムは初めから固定された山札から引くカードの列を持つということを意味する．

制約

すべての入力データは以下の条件を満たす．

• 1 \leqq Q \leqq 100．
• N = 900．
• A_{i,j} は 0 または 1 である (1 \leqq i \leqq Q, 1 \leqq j \leqq N)．

採点基準

この課題のテストケースの中で，1 つでも不正解 [1] ～ [4] (実装の詳細を参照) と判定されたものや， 実行時間制限超過，メモリ制限超過，実行時エラーと判定されたものがあった場合，0点となる．

またこの課題におけるすべてのテストケースに正解した場合，この課題のすべてのテストケースで， 関数 Anna の 1 回の呼び出しについて引数 0 \leqq x で関数 DrawCard を呼び出した回数の最大値を L として，以下のように採点される．

• 500 < L のとき，3 点
• 14 < L \leqq 500 のとき，\left\lfloor 100 \times \left(\dfrac{2.5}{L-11.5}\right)^{0.35} \right\rfloor 点
• L \leqq 14 のとき，100 点

やり取りの例

採点プログラムのサンプルが読み込む入力の例と，それに対応する関数の呼び出しの例を以下に示す．

入力例 1

2 5
0 1 0 0 1
1 1 0 1 0

この入力例は Q (=2) 回の占いからなり，2 回の占いでAnnaが山札から引くカードの枚数は N (=5) 枚である． この例では，1 回目の占いは Anna は次のような手順で占いを行う．

1. Anna が山札からカードを 1 枚引く．引いたカードに書かれた数は 0 である．
2. Anna は引いたカードを場に出して並べることを選択し，場に並べてあるカードの列の一番左に挿入する．場に並べられたカードの列は 0 になる．Anna は山札からカードを 1 枚引く，引いたカードに書かれた数は 1 である．
3. Anna は引いたカードを捨てることを選択する．Anna は山札からカードを 1 枚引く，引いたカードに書かれた数は 0 である．
4. Anna は引いたカードを場に出して並べることを選択し，場に並べてあるカードの列の左から 1 枚目のカードのすぐ右に挿入する．場に並べられたカードの列は 0,0 になる．Anna は山札からカードを 1 枚引く，引いたカードに書かれた数は 0 である．
5. Anna は引いたカードを捨てることを選択する．Anna は山札からカードを 1 枚引く，引いたカードに書かれた数は 1 である．
6. Anna は引いたカードを場に出して並べることを選択し，場に並べてあるカードの列の左から 1 枚目のカードのすぐ右に挿入する．場に並べられたカードの列は 0,1,0 になる．

Bruno は N の値と場に並べられたカードの列 0,1,0 をもとに，Anna が引いた 1 の書かれたカードの枚数が 2 であると答える． これは正しいため，占いは成功である．1回目の占いで Anna が場に出したカードの枚数 L は 3 である．

2 回目の占いで Anna が場に出したカードの枚数 L は 4 である．

この入力例は制約を満たさないことに注意すること． コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する． コンテストサイトからダウンロードできるファイルのうち，sample-02-in.txt は制約を満たす．

JOI 山脈にはたくさんの山が整列している． JOI 山脈は縦 H 行，横 W 列に区切られたマス目として表され， 縦方向は南北方向に平行であり，横方向は東西方向に平行である． 北から i 行目 (1 \leqq i \leqq H)，西から j 列目 (1\leqq j\leqq W) のマスのことをマス (i, j) と呼ぶ． 1 つのマスにはちょうど 1 つの山があり， マス (i, j) にある山の山頂の高さは T_{i, j} である．

ビ太郎のジャンプ力は L である．ビ太郎は山の山頂にいるとき， ハイジャンプ を行い，別の山の山頂に移動することができる． ハイジャンプ とは以下の操作を順に行うことを指す．

• 今いる山の山頂から真上に飛び上がる．今いる山の山頂の高さが x であったとき，ビ太郎はそのマスの高さ x + L + 0.5 の位置に浮遊する．
• 東西南北のいずれかに隣接するマスに高さを変えずに移動することを 0 回以上繰り返す．この際に訪れるすべてのマスについて，それらのマスにある山の山頂の高さは，ビ太郎が浮遊している高さより低くなければならない．
• 今いるマスにある山の山頂に着地する．

ビ太郎は Q 回の旅を計画している． k 回目 (1\leqq k \leqq Q) の旅の内容は， マス (A_{k}, B_{k}) にある山の山頂から マス (C_{k}, D_{k}) にある山の山頂へハイジャンプだけを使って移動するというものである． ビ太郎はこの旅を成功させることができるのかが知りたい．また，ハイジャンプの飛び上がる操作は非常に体力を使う操作であるため， 旅が成功するならば最小何回のハイジャンプが必要かが知りたい．

JOI 山脈の山とビ太郎のジャンプ力とビ太郎の旅の計画の情報が与えられたとき， それぞれの計画について， 旅が成功するか判定し，旅が成功するならば必要なハイジャンプの回数の最小値を求めるプログラムを作成せよ．

制約

• 1\leqq H．
• 1\leqq W．
• 2\leqq H\times W \leqq 300\,000．
• 1\leqq L\leqq 10^{9}．
• 1\leqq T_{i, j}\leqq 10^{9} (1\leqq i\leqq H,1\leqq j\leqq W)．
• 1\leqq Q \leqq 300\,000．
• 1\leqq A_{k} \leqq H (1\leqq k \leqq Q)．
• 1\leqq B_{k} \leqq W (1\leqq k \leqq Q)．
• 1\leqq C_{k} \leqq H (1\leqq k \leqq Q)．
• 1\leqq D_{k} \leqq W (1\leqq k \leqq Q)．
• (A_{k}, B_{k})\neq (C_{k}, D_{k}) (1\leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (10 点) H\times W \leqq 300，Q\leqq 150\,000．
2. (20 点) H\times W \leqq 3\,000，Q\leqq 150\,000．
3. (20 点) H\times W \leqq 150\,000，Q\leqq 150\,000，(A_{k}, B_{k}) = (1, 1) (1\leqq k \leqq Q)．
4. (30 点) H\times W \leqq 150\,000，Q\leqq 150\,000．
5. (20 点) 追加の制約はない．

入力例 1

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

出力例 1

3
-1
3
4
4
1

1 回目の旅の計画では以下のようにハイジャンプを 3 回することで，マス (1, 1) にある山の山頂からマス (2, 2) にある山の山頂へ移動することができる．

• 1 回目のハイジャンプ
  • マス (1, 1) にある山の山頂から真上に飛び上がる．このとき，ビ太郎の高さは 6.5 である．
  • マス (1, 2) に移動する．マス (1, 2) にある山の高さ 3 は 6.5 より小さいため移動が可能である．
  • マス (1, 2) にある山の山頂に着地する．
• 2 回目のハイジャンプ
  • マス (1, 2) にある山の山頂から真上に飛び上がる．このとき，ビ太郎の高さは 8.5 である．
  • マス (1, 1) に移動する．
  • マス (2, 1) に移動する．
  • マス (2, 1) にある山の山頂に着地する．
• 3 回目のハイジャンプ
  • マス (2, 1) にある山の山頂から真上に飛び上がる．このとき，ビ太郎の高さは 13.5 である．
  • マス (2, 2) に移動する．
  • マス (2, 2) にある山の山頂に着地する．

ハイジャンプをする回数を 3 回未満で 1 回目の旅を成功させることはできないので，1 行目には 3 を出力する．

2 回目の旅を成功させることはできないので，2 行目には -1 を出力する．

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

入力例 2

6 5 11
175 100 110 117 158
144 133 123 150 191
167 252 219 181 346
231 241 280 201 209
261 332 325 225 338
269 298 315 291 308
12
1 1 4 2
1 1 1 5
1 1 5 1
1 1 5 4
1 1 3 4
1 1 6 4
1 1 2 5
1 1 3 1
1 1 4 4
1 1 5 5
1 1 6 2
1 1 6 1

出力例 2

8
1
10
6
1
13
2
1
3
19
14
11

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

入力例 3

4 4 5
53 55 51 49
56 60 89 45
54 57 92 43
96 99 95 92
9
1 4 2 3
4 1 3 2
2 4 2 3
2 1 4 1
1 2 1 1
2 4 1 1
4 1 2 3
3 4 1 1
1 3 1 4

出力例 3

-1
1
-1
-1
1
3
1
4
1

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

IOI 王国は縦 L 行，横 L 列のマス目で表される領土を持っている．以降，上から i 行目 (1 \leqq i \leqq L)，左から j 列目 (1 \leqq j \leqq L) のマスをマス (i, j) と表すことにする．

最近の IOI 王国では感染症で倒れる患者が相次いでおり，国民から医療の充実を求める声が上がっている．そこで，IOI 王国の国王であるビ太郎は，マス (1, 1)，マス (1, L)，マス (L, 1)，マス (L, L) の 4 箇所に病院を建設し，それぞれの病院に 1 台ずつ救急車を設置することにした．

用心深いビ太郎は，実際に患者から救助要請があったときのことを想定してシミュレーションを行うことにした．ビ太郎が想定するシナリオでは，時刻 0 において N 人の患者から救助要請が届くので，時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを調べたい．k 番目 (1 \leqq k \leqq N) の患者はマス (X_k, Y_k) にいる．

救急車は以下の規則に従って患者を搬送する．

• それぞれの救急車は，時刻 0 以降に動き出すことができ，病院を出発し患者の存在するマスまで移動して患者を乗せ，再び病院まで移動して患者を降ろすことを繰り返す．
• それぞれの救急車は高々 1 人の患者を乗せることができる．
• それぞれの救急車は，その救急車が設置されている病院にしか患者を搬送することができず，病院が存在しないマスで患者を降ろしてはならない．
• それぞれの救急車は，1 単位時間かけて上下左右いずれかに隣接するマスに移動することができ，患者を乗せるのにかかる時間および降ろすのにかかる時間は無視できる．
• 異なる病院に設置されている救急車が同時に同じマスに存在することは可能である．

残念ながら，ビ太郎は自分の想定したシナリオの結果を調べることはできなかったため，あなたに代わりに調べるよう依頼してきた．

IOI 王国の領土の大きさおよびビ太郎が想定したシナリオの情報が与えられたとき，時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを求めるプログラムを作成せよ．

制約

• 3 \leqq L \leqq 10\, 000．
• 1 \leqq N \leqq 160．
• 1 \leqq T \leqq 20\, 000．
• 1 \leqq X_k \leqq L (1 \leqq k \leqq N)
• 1 \leqq Y_k \leqq L (1 \leqq k \leqq N)
• (X_k, Y_k) は (1, 1), (1, L), (L, 1), (L, L) のいずれでもない (1 \leqq k \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (4 点) T \leqq 50．
2. (8 点) T \leqq 160．
3. (5 点) N \leqq 10．
4. (18 点) N \leqq 20．
5. (15 点) N \leqq 45．L は奇数であり，Y_k = \frac{L+1}{2} (1 \leqq k \leqq N)．
6. (31 点) N \leqq 45．
7. (19 点) 追加の制約はない．

入力例 1

6 4 8
1 3
2 2
3 4
5 5

出力例 1

Yes

1 番目と 2 番目の患者をマス (1, 1) にある病院へ，3 番目の患者をマス (1, 6) にある病院へ，4 番目の患者をマス (6, 6) にある病院へそれぞれ搬送することで，時刻 8 までにすべての患者をいずれかの病院に搬送することができるので，Yes を出力する．

例えば，マス (1, 1) にある病院に設置された救急車が次の順に動くと，この救急車は時刻 8 までに 1 番目と 2 番目の患者を病院へ搬送することができる．

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

入力例 2

9 5 19
5 5
5 5
7 5
2 5
9 5

出力例 2

No

時刻 19 までにすべての患者をいずれかの病院に搬送することはできないので，No を出力する．

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

入力例 3

7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1

出力例 3

Yes

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

入力例 4

200 15 800
126 45
196 40
43 58
96 13
28 33
44 55
60 22
58 156
135 183
44 29
92 182
157 138
30 132
175 87
166 57

出力例 4

No

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

JOI 君が住む IOI 国は，大きな湖があることで有名である．今日，湖の周りでスタンプラリー大会が行われることになった．

湖の周りには等間隔に 2N 個の地点が並んでおり，時計回りに 1 から 2N までの番号が付けられている． また，隣り合う地点どうしを結ぶ 2N 本の 一方通行 の道がある． 道 i (1\leqq i \leqq 2N-1) は地点 i から地点 i+1 へ向かう道であり，道 2N は地点 2N から地点 1 へ向かう道である． それぞれの道の真ん中には 1 つのスタンプ台が設置されている．

スタンプには 1 から N までの N 色があり，道 i (1\leqq i \leqq 2N) の真ん中に設置されているスタンプ台で押すことのできるスタンプの色は A_i である． 各 j (1\leqq j \leqq N) について，色 j のスタンプを押すことのできるスタンプ台はちょうど 2 つある．

JOI 君はたくさんのスタンプカードを持ってスタンプラリー大会に参加することにした． それぞれのスタンプカードには左右 2 箇所にスタンプを押すことのできる枠が印刷されている． 1 つの枠にはスタンプを高々 1 つ押すことができる． はじめ，どのスタンプカードにもスタンプは押されていない． スタンプラリー大会での JOI 君の行動は以下の通りである．

1. まず，スタート地点として 2N 個の地点のいずれかを選び，その地点に移動する．地点 i (1\leqq i \leqq 2N) をスタート地点に選んだとき，JOI 君はスタンプラリー大会の参加費としてコスト C_i を支払う．
2. 次に，JOI 君は隣り合う道どうしに設置されているスタンプ台を交換するよう，運営会社に指示を出すことができる．すなわち，道 2N,1 に設置されているスタンプ台の交換，もしくは，i (2\leqq i \leqq 2N) を指定して道 i-1,i に設置されているスタンプ台の交換を指示することができる． JOI 君が指示を出す際に支払うコストは 1 回あたり X で， 何度でも 指示を出すことができる．一度も指示を出さないことも可能である．スタンプ台の交換は指示を出すたびにただちに実行される． ただし，不正防止のため，JOI 君が選んだスタート地点をまたぐようなスタンプ台の交換はできない．すなわち，JOI 君がスタート地点として地点 1 を選んだ場合は道 2N,1 に設置されているスタンプ台どうしの交換が，地点 i (2\leqq i \leqq 2N) を選んだ場合は道 i-1,i に設置されているスタンプ台どうしの交換が，禁止される．
3. その後，JOI 君はスタート地点を出発して時計回りに移動し，2N 個のスタンプ台を順に訪れ，スタート地点に戻ってきた段階でスタンプラリーを終了する．スタンプ台を訪れた際，JOI 君はスタンプカードにスタンプを何回でも押すことができる．同じスタンプ台で 1 枚のスタンプカードの左右にスタンプを押すことも可能である．ただし，それぞれのスタンプカードには必ず左，右の順番で押す必要がある．つまり，左側が空欄であるスタンプカードの右側にスタンプを押すことはできない．

JOI 君はできる限り多くの種類の，左右両方の枠にスタンプが押されたスタンプカードを集めたい． 左側に色 a，右側に色 b のスタンプが押されたスタンプカードをスタンプカード (a,b) と表すこととする． このとき，スタンプカード (a_1, b_1) と (a_2, b_2) は，a_1=a_2 かつ b_1=b_2 のとき，またそのときに限り，種類が同じであるとみなす．

N 色のスタンプがあるため，左右両方の枠にスタンプが押されたスタンプカードは全部で N^2 種類あることに注意せよ．

あなたは JOI 君の戦略作りを手伝うために，Q 個の質問に答える必要がある． q 個目 (1\leqq q \leqq Q) の質問は以下である．

• スタンプラリーの終了時点で，左右両方の枠にスタンプが押されたスタンプカードを K_q 種類以上持っているために支払う必要のあるコストの合計の最小値はいくらか？なお，本問の制約下では，十分多くのコストを支払うことで左右両方の枠にスタンプが押されたスタンプカードを K_q 種類以上集められることが証明できる．

スタンプの色，スタンプラリー大会の参加費，運営会社に指示を出す際に支払うコスト，および JOI 君の質問についての情報が与えられたとき，JOI 君の Q 個の質問の答えを計算するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 500\,000．
• 1 \leqq X \leqq 500\,000．
• (A_1, A_2, \dots, A_{2N}) は (1, 1, 2, 2, \dots, N, N) の並べ替えである．
• 1 \leqq C_i \leqq 10^{18} (1 \leqq i \leqq 2N)．
• 1 \leqq Q \leqq 500\,000．
• 1 \leqq K_q \leqq N^2 (1\leqq q \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (5 点) N\leqq 4．
2. (20 点) N\leqq 5000，Q = 1，K_1=N^2．
3. (20 点) N\leqq 5000，Q = 1．
4. (19 点) N\leqq 5000．
5. (21 点) Q = 1．
6. (15 点) 追加の制約はない．

入力例 1

3 2
1 2 2 3 1 3
6 1 4 5 4 7
2
8
9

出力例 1

3
4

JOI 君がスタート地点として地点 2 を選び，道 3 に設置されているスタンプ台と道 4 に設置されているスタンプ台との交換を指示した場合を考える． このとき，

• JOI 君が支払うコストの合計は C_2+X\times 1 = 3 である．
• JOI 君は道 2,3,4,5,6,1 の順にスタンプ台を訪れ，それぞれのスタンプ台で押すことのできるスタンプの色は，順に色 2, 3, 2, 1, 3, 1 となる．
• JOI 君が最終的に持っている可能性のある，左右両方の枠にスタンプが押されたスタンプカードは 8 種類となる．
  • 例えば，左側に色 3 のスタンプ，右側に色 1 のスタンプが押されたスタンプカードを得るためには，道 3 でスタンプカードの左側に，道 1 でスタンプカードの右側に，それぞれスタンプを押せばよい．
  • 左側に色 1 のスタンプ，右側に色 2 のスタンプが押されたスタンプカードだけは得られないことに注意せよ．

2 以下のコストで 8 種類以上のスタンプカードを得ることはできないため，1 行目には 3 を出力する．

また，JOI 君がスタート地点として地点 3 を選び，スタンプ台の交換を指示しなかった場合には，9 種類のスタンプカードを得ることができる． このときに JOI 君が支払うコストの合計は C_3 + X\times 0 = 4 である．

3 以下のコストで 9 種類以上のスタンプカードを得ることはできないため，2 行目には 4 を出力する．

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

入力例 2

8 1
1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8
4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7
1
64

出力例 2

7

スタート地点として地点 10 を選び，次の順にスタンプ台の交換を指示した場合を考える．

• 道 15 に設置されているスタンプ台と道 16 に設置されているスタンプ台との交換
• 道 2 に設置されているスタンプ台と道 3 に設置されているスタンプ台との交換
• 道 16 に設置されているスタンプ台と道 1 に設置されているスタンプ台との交換
• 道 1 に設置されているスタンプ台と道 2 に設置されているスタンプ台との交換

このとき 64 種類のスタンプカードを得ることができ，支払うコストの合計は C_{10}+X\times 4=7 である．

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

入力例 3

9 4
4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7
12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8
6
39
81
73
79
64
52

出力例 3

1
18
3
10
1
1

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

あなたは JOI 銀河で怪盗として活躍している．

JOI 銀河には 0 から N - 1 までの番号が付けられている N 個の星がある．また，0 から M - 1 までの番号が付けられている M 個のワープ装置がある．ワープ装置 i (0 \leqq i \leqq M - 1) は星 U_i と星 V_i の間を双方向に結んでいる．どの 2 つの星の間も，いくつかのワープ装置を用いることで移動できる．

JOI 銀河のある星には鍵が隠されており，別の星には宝箱が隠されている．あなたのミッションは，鍵と宝箱が隠されている星の番号を特定することである．そのために，以下の質問を 300 回まで行うことができる．

• それぞれのワープ装置 i (0 \leqq i \leqq M - 1) について，星 U_i から星 V_i へ一方向のみに結ぶようにするか星 V_i から星 U_i へ一方向のみに結ぶようにするかを選択する．
• そのもとで，いくつかのワープ装置を用いて鍵のある星から宝箱のある星へ移動できるかを尋ねる．

あなたは質問を行うことで，鍵が隠された星の番号である A と宝箱が隠された星の番号である B を特定したい．ミッションで高い評価を得るために，質問の回数はできるだけ少なくしたい．

銀河の情報が与えられたとき，質問を行うことで，鍵が隠された星の番号 A と宝箱が隠された星の番号 B を特定するあなたの戦略を実装したプログラムを作成せよ．

実装の詳細

あなたは 1 つのファイルを提出しなければならない．

あなたの提出するファイルは thief.cpp という名前である．thief.cpp は #include プリプロセッサ指令によって thief.h を読み込み，以下の関数を実装していなければならない．

• void solve(int N, int M, std::vector<int> U, std::vector<int> V)
  • この関数は各テストケースにおいて 1 回だけ呼び出される．
  • 引数 N は星の個数 N である．
  • 引数 M はワープ装置の個数 M である．
  • 引数 U, V は長さ N の配列であり，0 \leqq i \leqq M - 1 について，U[i], V[i] はワープ装置 i が双方向に結ぶ星の番号 U_i, V_i である．

thief.cpp 内では以下の関数を呼び出すことができる．

• int query(std::vector<int> x)
  • この関数を用いて，質問を行う．
  • 引数 x は長さ M の配列である．0 \leqq i \leqq M - 1 について，x[i] が 0 のときワープ装置 i について，星 U_i から星 V_i へ一方向に結ぶようにすることを，1 のときワープ装置 i について，星 V_i から星 U_i へ一方向に結ぶようにすることを表す．
  • 戻り値は 0 または 1 である．戻り値が 0 のときいくつかのワープ装置を用いて星 A から星 B へ移動できないことを，1 のとき星 A から星 B へ移動できることを表す．
  • 引数 x の長さは M でなければならない．これが満たされていない場合，不正解 [1] と判定される．
  • 引数 x の各要素は，0 または 1 でなければならない．これが満たされていない場合，不正解 [2] と判定される．
  • 関数 query を 300 回を超えて呼び出してはならない．300 回を超えて呼び出した場合，不正解 [3] と判定される．
• void answer(int A, int B)
  • この関数を用いて，鍵が隠された星の番号と宝箱が隠された星の番号を解答する．
  • 引数 A は，0 以上 N - 1 以下の整数である．鍵が隠された星の番号 A を表す．
  • 引数 A は，0 以上 N - 1 以下でなければならない．これが満たされていない場合，不正解 [4] と判定される．
  • 引数 B は，0 以上 N - 1 以下の整数である．宝箱が隠された星の番号 B を表す．
  • 引数 B は，0 以上 N - 1 以下でなければならない．これが満たされていない場合，不正解 [5] と判定される．
  • 誤った星の番号を解答した場合，不正解 [6] と判定される．
  • 関数 answer はちょうど 1 回呼び出さなければならない．関数 answer を 2 回以上呼び出した場合，不正解 [7] と判定される．関数 solve の実行の終了時に関数 answer が 1 回も呼び出されていなかった場合，不正解 [8] と判定される．

重要な注意

• 内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．
• あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

作成したプログラムをテストするための，採点プログラムのサンプルが， コンテストサイトからダウンロードできるアーカイブの中に含まれている． このアーカイブには，提出しなければならないファイルのサンプルも含まれている．

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である． 作成したプログラムをテストするには， これらのファイル grader.cpp, thief.cpp, thief.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること． 採点プログラムのサンプルは単一のプロセスとして起動する． このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

採点に関する注意

いくつかのテストケースについて，実際の採点プログラムは適応的 (adaptive) である． これは，採点プログラムは初めから固定された答えを持たず，それ以前の query 関数の呼び出しに応じて採点プログラムが応答するということである． ただし，すべての応答に矛盾しないような答えが少なくとも 1 つ存在するということが保証される．

制約

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 10\,000．
• 1 \leqq M \leqq 15\,000．
• 0 \leqq A \leqq N - 1．
• 0 \leqq B \leqq N - 1．
• A \neq B．
• 0 \leqq U_i < V_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
• (U_i, V_i) \neq (U_j, V_j) (0 \leqq i < j \leqq M - 1)．
• どの 2 つの星の間も，いくつかのワープ装置を用いることで移動できる．

小課題

1. (7 点) M = N - 1，U_i = i，V_i = i + 1 (0 \leqq i \leqq M - 1)．
2. (13 点) M = N - 1，U_i = 0，V_i = i + 1 (0 \leqq i \leqq M - 1)．
3. (2 点) M = N - 1，N \leqq 8．
4. (8 点) M = N - 1，N \leqq 50．
5. (5 点) M = N - 1，N \leqq 150．
6. (5 点) M = N - 1，N \leqq 250．
7. (40 点) M = N - 1．この小課題では，以下に従い得点が決定される．
   • 小課題 7 に対応するテストケースについて，1 つでも不正解があった場合，この小課題の得点は 0 点となる．
   • そうでない場合，この小課題のすべてのテストケースにおける，関数 query の呼び出し回数の最大値を T とする．このとき，小課題の得点は以下のように決定される．
     • 120 < T のとき，20 点．
     • 70 < T \leqq 120 のとき，30 点．
     • T \leqq 70 のとき，40 点．
8. (20 点) 追加の制約はない．この小課題では，以下に従い得点が決定される．
   • 小課題 8 に対応するテストケースについて，1 つでも不正解があった場合，この小課題の得点は 0 点となる．
   • そうでない場合，この小課題のすべてのテストケースにおける，関数 query の呼び出し回数の最大値を T とする．このとき，小課題の得点は以下のように決定される．
     • 120 < T のとき，10 点．
     • 70 < T \leqq 120 のとき，15 点．
     • T \leqq 70 のとき，20 点．

小課題 1,2,3,4,5,6 の得点は関数 query の呼び出し回数によらない (300 回以下であればよい) が，70 回より多い場合はコンテストサイトにおいて「出力は部分的に正しい」と表記されることがある．

やりとりの例

入力例 1

5 4 0 4
0 1
0 3
1 2
1 4

1 回目の query 関数の呼び出しに対応する選択は以下のようになる．

• ワープ装置 0 について，星 0 から星 1 へ一方向に結ぶようにする．
• ワープ装置 1 について，星 3 から星 0 へ一方向に結ぶようにする．
• ワープ装置 2 について，星 1 から星 2 へ一方向に結ぶようにする．
• ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはワープ装置 0, 3 をこの順に用いることで移動できるため，戻り値は 1 となる．

2 回目の query 関数の呼び出しに対応する選択は以下のようになる．

• ワープ装置 0 について，星 1 から星 0 へ一方向に結ぶようにする．
• ワープ装置 1 について，星 3 から星 0 へ一方向に結ぶようにする．
• ワープ装置 2 について，星 2 から星 1 へ一方向に結ぶようにする．
• ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため，戻り値は 0 となる．

3 回目の query 関数の呼び出しに対応する選択は以下のようになる．

• ワープ装置 0 について，星 0 から星 1 へ一方向に結ぶようにする．
• ワープ装置 1 について，星 0 から星 3 へ一方向に結ぶようにする．
• ワープ装置 2 について，星 2 から星 1 へ一方向に結ぶようにする．
• ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できるため，戻り値は 1 となる．

4 回目の query 関数の呼び出しに対応する選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため，戻り値は 0 となる．

answer 関数の呼び出しでは星 A が星 0 であり，星 B が星 4 であると解答したことを表している．

この入力例は小課題 3,4,5,6,7,8 の制約を満たす．コンテストサイトからダウンロードできるアーカイブの中に含まれているファイルのうち，sample-01-in.txt は入力例 1 に対応する．

なお，コンテストサイトからダウンロードできるアーカイブの中に含まれている，提出しなければならないファイルのサンプルにおける関数の呼び出しは，これらの関数の呼び出しと同じである．

勇者ビ太郎は，モンスターから村を守る防衛戦のクエストに挑もうとしている． 防衛戦の難易度は 1 以上 L 以下の整数で表され，この値は挑戦時に選択することができる． 難易度 \ell (1 \leqq \ell \leqq L) の防衛戦では，出現するモンスターの HP が (難易度 1 の場合を基準として) \ell 倍になる．

防衛戦は T 秒間行われ，N 体のモンスターが次々と現れる． モンスターには 1 から N までの番号が付けられている． 防衛戦が開始されてから t 秒後 (0 \leqq t \leqq T) のことを，時刻 t と呼ぶ． モンスター i (1 \leqq i \leqq N) は時刻 S_i (0 \leqq S_i < T) に出現し， その強さは P_i で，その HP は，防衛戦の難易度を \ell として，\ell \times H_i である．

防衛戦の間，ビ太郎は以下の操作を何度でも行うことができる．

• 現在出現しているモンスターの中から 1 体を選び，1 秒かけてそのモンスターに攻撃する．そのモンスターの HP は 1 減少する．HP が 0 になったモンスターは倒れ，これ以上攻撃することはできない．

時刻 T になると防衛戦は終了し，防衛戦の 評価値 が以下のように計算される．

• 時刻 T の直後の時点でのモンスター i (1 \leqq i \leqq N) の HP を h_i とすると，評価値は h_1 P_1 + h_2 P_2 + \dots + h_N P_N である．

評価値がクエストにより定められた基準値 m 以下であるとき，かつそのときに限り，ビ太郎はクエストを達成することができる．

より高い難易度でクエストを達成するほど報酬も豪華になるため，ビ太郎は，クエストを達成することができる最大の難易度を求めたい． しかし，基準値は事前には知らされないため，ビ太郎は，Q 個の基準値の候補 M_1, M_2, \dots, M_Q について， クエストを達成することができる最大の難易度を求めることにした．

防衛戦の情報と基準値の候補の情報が与えられたとき，それぞれの基準値の候補について，クエストを達成することが可能かどうか判定し， 可能な場合は，クエストを達成することができる最大の難易度を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 6\,000．
• 1 \leqq L \leqq 10\,000\,000．
• 1 \leqq T \leqq 10^{18}．
• 0 \leqq S_i < T (1 \leqq i \leqq N)．
• 1 \leqq H_i (1 \leqq i \leqq N)．
• 1 \leqq P_i (1 \leqq i \leqq N)．
• H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leqq 10^{11}．
• 1 \leqq Q \leqq 1\,000\,000．
• 0 \leqq M_j \leqq 10^{18} (1 \leqq j \leqq Q)．
• M_1 < M_2 < \cdots < M_Q．
• 入力される値はすべて整数である．

小課題

1. (1 点) N \leqq 30，Q = 1，M_1 = 0，L = 1．
2. (3 点) N \leqq 30，Q = 1，M_1 = 0．
3. (10 点) N \leqq 30，Q \leqq 3．
4. (10 点) Q \leqq 3．
5. (35 点) N \leqq 30．
6. (8 点) N \leqq 400．
7. (20 点) N \leqq 1\,800．
8. (13 点) 追加の制約はない．

入力例 1

2 2 10
0 9 2
8 5 1
3
0
20
40

出力例 1

0
1
2

難易度 1 の防衛戦では，以下のように行動することで評価値 4 を達成することができる．評価値 3 以下を達成することはできない．

また，難易度 2 の防衛戦では，以下のように行動することで評価値 26 を達成することができる．評価値 25 以下を達成することはできない．

さらに，この入力例においては L = 2 であるため，難易度 3 以上の防衛戦を選択することができない．したがって，出力は以下のようになる．

• 1 個目の基準値 M_1 = 0 ではどの難易度でもクエストを達成することができないため，1 行目には 0 を出力する．
• 2 個目の基準値 M_2 = 20 では最大で難易度 1 の防衛戦までクエストを達成することができるため，2 行目には 1 を出力する．
• 3 個目の基準値 M_3 = 40 では最大で難易度 2 の防衛戦までクエストを達成することができるため，3 行目には 2 を出力する．

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

入力例 2

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

出力例 2

0

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

入力例 3

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

出力例 3

7000000

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

入力例 4

5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500

出力例 4

6
8
10
12
13
15
16
18
19
20
20

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

入力例 5

15 10000000 1000000000000
160278118759 43084 33592
442653603914 19490 23090
824219815410 50858 89563
502303340628 56629 45080
495062829942 87342 28821
234536700105 45384 34328
396080693809 78081 50812
734374391045 40873 92012
122606844331 25451 30426
204076581972 58431 13989
495156368673 54276 41670
812963939390 27614 50228
405067019838 96324 18477
464546304875 67562 45956
528559327980 41759 15546
10
216000000000000
1728000000000000
5832000000000000
13824000000000000
27000000000000000
46656000000000000
74088000000000000
110592000000000000
157464000000000000
216000000000000000

出力例 5

995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125

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

K 理事長は N 日間の会議を運営する予定である． 1 日に会議は 1 つ開催され，メインの会場 A とサブの会場 B, C のいずれか 1 つが使用される．

各会議の会場に関する情報は A, B, C, ? からなる文字列 S で与えられる． i 日目 (1\leqq i \leqq N) の会議の会場は，S の i 文字目が A の場合は会場 A，B の場合は会場 B，C の場合は会場 C，? の場合は未定である．ただし， 1 日目と N 日目の会議は多くの人が参加するため，会場 A が使われることが決まっている．

これから K 理事長は，会場が未定の会議について，それぞれ会場 A, B, C のいずれか 1 つを割り当てようとしている． また，移動の負担を減らすために，j 日目と j+1 日目で会議の会場が異なるような j (1\leqq j \leqq N-1) の個数を最小にしたいと考えている．

会場が未定の会議の割り当てについて，Q 個のシナリオを検討し，上記の個数の最小化を考えたい． k 番目 (1 \leqq k \leqq Q) のシナリオとそれに対応する質問は以下の通りである．

• 会場が未定の会議について，X_k 個に会場 A を，Y_k 個に会場 B を，Z_k 個に会場 C を割り当てることにする．この時，j 日目と j+1 日目で会議の会場が異なるような j の個数の最小値を求めよ．

会場の情報，また検討すべきシナリオの情報が与えられたとき，質問に回答するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 300\,000．
• S は A, B, C, ? からなる長さ N の文字列である．
• S の 1 文字目と N 文字目 は A である．
• 1 \leqq Q \leqq 200\,000．
• 0 \leqq X_k (1\leqq k \leqq Q)．
• 0 \leqq Y_k (1\leqq k \leqq Q)．
• 0 \leqq Z_k (1\leqq k \leqq Q)．
• X_k + Y_k + Z_k は S に含まれる ? の個数と等しい (1\leqq k \leqq Q)．
• N, Q, X_k, Y_k, Z_kは整数である (1\leqq k \leqq Q)．

小課題

1. (4 点) N \leqq 50，S に含まれる ? の個数は 13 以下．
2. (7 点) N \leqq 500．
3. (13 点) N \leqq 5\,000，Q \leqq 10．
4. (18 点) N \leqq 5\,000．
5. (12 点) Q \leqq 10．
6. (8 点) S に C は含まれない，Z_k = 0 (1\leqq k \leqq Q)．
7. (13 点) Z_k = 0 (1\leqq k \leqq Q)．
8. (25 点) 追加の制約はない．

入力例 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

出力例 1

3
4
4

1 番目のシナリオでは，会場が未定の会議 5 個のうち， 1 個に会場 A を， 3 個に会場 B を， 1 個に会場 C を割り当てる． 例えば，各会議の会場に関する情報が ABBBBCCAA となるような割り当て方が考えられる．この場合， j 日目と j+1 日目で会議の会場が異なるような j は 1,5,7 の 3 個となる． j の個数を 2 個以下にするような方法は存在しないため， 1 行目には 3 を出力する．

2 番目のシナリオでは，会場が未定の会議 5 個のうち， 4 個に会場 A を， 1 個に会場 B を割り当てる． 例えば，各会議の会場に関する情報が AAABBACAA となるような割り当て方が考えられる．この場合，j 日目と j+1 日目で会議の会場が異なるような j は 3,5,6,7 の 4 個となる． j の個数を 3 個以下にするような方法は存在しないため， 2 行目には 4 を出力する．

3 番目のシナリオでは，会場が未定の会議 5 個のうち， すべてに会場 C を割り当てる． j 日目と j+1 日目で会議の会場が異なるような j は 1,3,4,8 の 4 個となり， 3 行目には 4 を出力する．

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

入力例 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

出力例 2

4
4
2
2

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

入力例 3

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

出力例 3

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17

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

K 理事長は春季トレーニングの参加者にゲームを用意した．

春季トレーニングには N 人の参加者がおり，それぞれ 1 から N までの番号が付けられている． それぞれの参加者は 1 つボードを持っている． ゲームは以下の手順で行われる．

1. K 理事長は，N 人の参加者の中から 親 となる参加者を 1 人選ぶ．親でない参加者は 子 となる．どの参加者が親であるかは，参加者には伝えられない．
2. K 理事長は，親のボードに文字 T を，すべての子のボードに文字 F を書く．
3. 各参加者は自分のボードに書かれた文字を読む． その後，参加者の間で事前に定めた 戦略 に従って，以下のターンを L 回行う．
   1. 各参加者は自分のボードに書かれた文字を消し，新たに T か F を書き込む．その後，各参加者はボードを K 理事長に渡す．
   2. i = 1, 2, \dots, N について，以下を行う．
      • 参加者 i は，ある参加者 p (1 \leqq \mathit{p} \leqq N) を指定し，その番号 \mathit{p} を K 理事長に伝える．K 理事長は，参加者 \mathit{p} のボードを参加者 i に見せ，そのボードに書かれた文字を参加者 i は読む．このとき，参加者 i は自分自身を指定してもよい．
4. 各参加者は，誰が親であるかを答える．

戦略を事前にうまく定めておくことによって，親としてどの参加者が選ばれたとしても，最終的に全員が親である参加者の番号を答えられるようにすることがこのゲームの目標である． また，できるだけ小さいターン数 L で目標を達成したい．

戦略 とは，ターン数を表す非負整数 L および参加者の行動を決定する以下のような方法の組である．

• 参加者 i (1 \leqq i \leqq N) が，t ターン目 (1 \leqq t \leqq L) が始まるまでに読んだ文字が順に a_0,a_1,\ldots,a_{t - 1} であったとき，それらの情報 (i,t,a_0,a_1,\ldots,a_{t - 1}) のみから，参加者 i が t ターン目でボードに書く文字および指定する参加者の番号を定める方法．
• 参加者 i (1 \leqq i \leqq N) が，L ターン目の終了までに読んだ文字が順に a_0,a_1,\ldots,a_{L} であったとき，それらの情報 (i,L,a_0,a_1,\ldots,a_{L}) のみから，参加者 i が最終的に答える参加者の番号を定める方法．

目標を達成できるようなある戦略を定め，その戦略に従ったときに，親が 1,2,\ldots,N だった場合のそれぞれについて，各参加者が各ターンにおいてボードに書く値および次に指定する参加者を出力せよ．

制約

• N は 4,32,48 のいずれかである．

採点基準

3 個の入力データの得点の合計が課題の得点である．

各入力データに対し，得点は以下のように計算される．

あなたの出力が誤っている場合，すなわちフォーマットが間違っている場合や，「目標を達成できるようなある戦略が存在して，出力がその戦略に従った結果である」という条件が満たされないとき，あなたの得点は 0 点となる．

あなたの出力が正しい場合，以下で定める点数となる．

各入力データにおける，N の値と配点は，以下の通りである．

ただし，0 点の場合，採点システム上では 出力は正しくない と表示されることに注意せよ．

入力例 1

3

出力例 1

3
1
T 1 T 2 T 3
F 1 F 2 F 3
F 1 F 2 F 3
2
F 1 F 2 F 3
T 1 T 2 T 3
F 1 F 2 F 3
3
F 1 F 2 F 3
F 1 F 2 F 3
T 1 T 2 T 3

この出力例は，以下のような戦略に従った結果である．

• L = 3 とする．
• 参加者 i (1 \leqq i \leqq N) は，t (1 \leqq t \leqq L) ターン目では，自分が親であるならば T を，子であるならば F をボードに書く．自分が親であるかどうかは，初めに K 理事長によって自分のボードに書かれた文字を読むことで分かることに注意せよ．
• 参加者 i (1 \leqq i \leqq N) は，t (1 \leqq t \leqq L) ターン目では，これまでに読んだ文字の情報に関わらず参加者 t を指定する．
• それぞれの参加者は，3 ターン目の終了時点で，自分を含むすべての参加者がボードに書いた文字を 1 回以上ずつ読んでいる．それぞれの参加者は，ボードに T と書いていた参加者の番号を最終的に答える．

この戦略に従った結果，親としてどの参加者が選ばれたとしても，最終的に全員が親である参加者の番号を正しく答えることができており，目標が達成されている． そのため，この出力例は正しいと判定される．

この入力例は制約を満たさず，また実際の入力データに含まれないことに注意せよ．

実装の詳細

あなたは 1 つのファイルを提出しなければならない．

あなたの提出するファイルは circuit.cpp という名前である． そのプログラムは #include プリプロセッサ指令によって circuit.h を読み込むこと．

circuit.cpp は以下の関数を実装していなければならない．

• std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)
  • この関数は各テストケースにおいて 1 回だけ呼び出される．
  • 引数 N は部品スロットの個数 N である．
  • 引数 R は設置されている OR 部品の個数の上限 R である．
  • 引数 U，V は長さ N の配列であり，U[i]，V[i] (0 \leqq i \leqq N - 1) は部品スロット i に接続されているスイッチの番号 U_{i}, V_{i} である．
  • この関数は，以下の条件を満たす & と | からなる長さ N の文字列 t を返さなければならない．
    • 各 i = 0, 1, \dots, N-1 について，部品スロット i に設置されている部品が AND 部品ならば t[i] は & であり，OR 部品ならば t[i] は | である．
  • 戻り値 t の長さが N でない場合，不正解[1] と判定される．
  • 戻り値 t に & でも | でもない文字が含まれる場合，不正解[2] と判定される．
  • 実際に各部品スロットに設置されている部品の種類が，戻り値 t の表すものと異なる場合，不正解[3] と判定される．

あなたのプログラムは以下の関数を呼び出すことができる．

• int query(std::string s)
  • あなたはこの関数を用いて JOI 君に質問をすることができる．
  • 引数 s は 0 と 1 からなる長さ 2N + 1 の文字列でなければならない．各 j = 0, 1, \dots, 2N について，s[j] が 0 ならばスイッチ j を OFF にすることを，s[j] が 1 ならばスイッチ j を ON にすることを表す．
  • 引数 s の長さが 2N+1 でない場合，不正解[4] と判定される．
  • 引数 s に 0 でも 1 でもない文字が含まれる場合，不正解[5] と判定される．
  • この関数を 1\,000 回より多く呼び出してはならない．1\,000 回より多く呼び出した場合，不正解[6] と判定される．
  • この関数の戻り値は，引数 s の通りにスイッチの状態を変更したときの回路ボードの出力である．

重要な注意

• 内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．
• あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

作成したプログラムをテストするための，採点プログラムのサンプルが， コンテストサイトからダウンロードできるアーカイブの中に含まれている． このアーカイブには，提出しなければならないファイルのサンプルも含まれている．

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である． 作成したプログラムをテストするには， これらのファイル grader.cpp, circuit.cpp, circuit.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp circuit.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること． 採点プログラムのサンプルは単一のプロセスとして起動する． このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

採点に関する注意

実際の採点プログラムは適応的 (adaptive) ではなく，やりとりの初めから固定された答えを持つ．

制約

• 1 \leqq N \leqq 8\,000．
• 1 \leqq R \leqq \min(N, 120)．
• i < U_i < V_i \leqq 2N (0 \leqq i \leqq N - 1)．
• j = 1, 2, \dots, 2N について，U_i = j または V_i = j であるような i (0 \leqq i \leqq N - 1) がただ 1 つ存在する．

小課題

1. (1 点) N = 1．
2. (4 点) N \leqq 1\,000，R = 1．
3. (5 点) N \leqq 1\,000．
4. (17 点) U_i = i + 1，V_i = N + 1 + i (0 \leqq i \leqq N - 1)，R \leqq 70．
5. (8 点) U_i = i + 1，V_i = N + 1 + i (0 \leqq i \leqq N - 1)．
6. (23 点) U_i = 2i + 1，V_i = 2i + 2 (0 \leqq i \leqq N - 1)，R \leqq 70．
7. (8 点) U_i = 2i + 1，V_i = 2i + 2 (0 \leqq i \leqq N - 1)．
8. (27 点) R \leqq 70．
9. (7 点) 追加の制約はない．

やりとりの例

採点プログラムのサンプルが読み込む入力の例と，それに対応する関数の呼び出しの例を以下に示す．

入力例 1

1 1
1 2
|

1 回目の query の呼び出しでは，回路ボードの出力は以下のように計算できる．

• スイッチ 1, 2 の状態はそれぞれ ON, OFF であるから，スイッチ 1, 2 はそれぞれ 1, 0 を出力する．
• 部品スロット 0 には OR 部品が設置されていて，接続するスイッチ 1, 2 はそれぞれ 1, 0 を出力しているから，部品スロット 0 は \max(1, 0) = 1 を出力する．
• スイッチ 0 の状態は OFF で，部品スロット 0 の出力は 1 であるから，スイッチ 0 の出力は 1 である．
• したがって，回路ボードの出力は 1 である．

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

入力例 2

3 3
1 2
3 4
5 6
&&|

問題文中の図がこの入力例の回路ボードを表している．

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

コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応し，sample-02-in.txt は入力例 2 に対応する． また，sample-03-in.txt は小課題 3, 4, 5, 8, 9 の制約を満たし，sample-04-in.txt は小課題 3, 6, 7, 8, 9 の制約を満たす．

JOI 国には N 個の街があり，街には 1 から N までの番号が付けられている． これらの街の間を結ぶ N-1 本の 一方通行 の道路がある． 具体的には，各 i = 2, 3, \ldots, N について，街 i から街 P_i に向かう道路がある． ここで，1 \leqq P_i < i が保証される．

N 個の街にはそれぞれ 危険度 が定義されている． 首都である街 1 の危険度は 0 である． 街 i (2\leqq i \leqq N) の危険度は，街 i から街 1 へ向かう経路において通る道路の本数として定義される． ここで，JOI 国の構造上，街 i から街 1 へ向かう経路はちょうど 1 つ存在することに注意せよ．

現在街 i (1\leqq i \leqq N) には K_i 匹のビーバーが住んでいる． JOI 国の大統領であるビ太郎はビーバーたちの移住計画を立てた． 移住計画はこれから Q 日間にわたって実行される． j 日目 (1\leqq j \leqq Q) には次の 3 種類のうちいずれか 1 つのイベントが発生する．

• 移住
  その時点で危険度 X_j の街に住んでいるビーバー全員が，各々が住んでいる街から何本かの道路を通ってたどり着くことのできる危険度 Y_j の街へ移住する．ここで，0\leqq Y_j < X_j が保証される．JOI 国の構造上，各ビーバーについて，移住先が一意に定まることに注意せよ．

• 移民受け入れ
  JOI 国外からの移民を受け入れることで，街 A_j に住むビーバーの数が L_j だけ増加する．

• 調査
  その時点で街 B_j に住んでいるビーバーの数を調査する．

ビ太郎の部下であるあなたは，各調査イベントにおいて実際にその街を訪れなくとも移住計画の情報のみによってビーバーの数を計算できることに気づいた．

JOI 国の構造，現在住んでいるビーバーの数，および移住計画についての情報が与えられたとき，各調査イベントの結果を計算するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 2\,000\,000．
• 1 \leqq P_i < i (2 \leqq i \leqq N)．
• 0 \leqq K_i \leqq 100 (1 \leqq i \leqq N)．
• 1 \leqq Q \leqq 2\,000\,000．
• T_j は 1, 2, 3 のいずれかである (1\leqq j \leqq Q)．
• T_j=1 のとき，0 \leqq Y_j < X_j \leqq N-1 (1\leqq j \leqq Q)．
• T_j=2 のとき，1\leqq A_j \leqq N，1 \leqq L_j \leqq 100 (1\leqq j \leqq Q)．
• T_j=3 のとき， 1 \leqq B_j \leqq N (1\leqq j \leqq Q)．
• T_j=3 となる j (1\leqq j \leqq Q) が 1 つ以上存在する．
• 入力される値はすべて整数である．

小課題

街の危険度の最大値を D とする．

1. (4 点) D = 1．
2. (8 点) N \leqq 20．
3. (13 点) D\leqq 20．
4. (15 点) T_j\neq 2 (1\leqq j\leqq Q)．さらに，T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下．
5. (15 点) T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下．
6. (27 点) T_j\neq 2 (1\leqq j\leqq Q)．
7. (18 点) 追加の制約はない．

入力例 1

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

出力例 1

1
8
0
3

最初，街 1,2,3,4 にはそれぞれ 1,3,4,3 匹のビーバーが住んでいる． また，各街の危険度はそれぞれ 0,1,1,2 である．

1 日目は調査イベントが発生する． したがって，1 行目にはその時点で街 1 に住むビーバーの数である 1 を出力する．

2 日目は移住イベントが発生する． その時点で街 2 に住んでいるビーバーは街 1 に移動する． また，その時点で街 3 に住んでいるビーバーも街 1 に移動する． 2 日目の終了時点で，街 1,2,3,4 にはそれぞれ 8,0,0,3 匹のビーバーが住んでいる．

3 日目は調査イベントが発生する． したがって，2 行目にはその時点で街 1 に住むビーバーの数である 8 を出力する．

4 日目は調査イベントが発生する． したがって，3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する．

5 日目は移住イベントが発生する． その時点で街 4 に住んでいるビーバーは街 2 に移動する． 5 日目の終了時点で，街 1,2,3,4 にはそれぞれ 8,3,0,0 匹のビーバーが住んでいる．

6 日目は調査イベントが発生する． したがって，4 行目にはその時点で街 2 に住むビーバーの数である 3 を出力する．

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

入力例 2

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

出力例 2

3
13
0
4
0
17

最初，街 1,2,3 にはそれぞれ 3,1,4 匹のビーバーが住んでいる． また，各街の危険度はそれぞれ 0,1,1 である．

1 日目は移民受け入れイベントが発生する． 街 2 に住むビーバーの数が 5 だけ増える． 1 日目の終了時点で，街 1,2,3 にはそれぞれ 3,6,4 匹のビーバーが住んでいる．

2 日目は移住イベントが発生する． その時点で危険度が 2 の街に住んでいるビーバーはいないため，移動は起こらない．

3 日目は調査イベントが発生する． したがって，1 行目にはその時点で街 1 に住むビーバーの数である 3 を出力する．

4 日目は移住イベントが発生する． その時点で街 2 に住んでいるビーバーは街 1 に移動する． また，その時点で街 3 に住んでいるビーバーも街 1 に移動する． 4 日目の終了時点で，街 1,2,3 にはそれぞれ 13,0,0 匹のビーバーが住んでいる．

5 日目は調査イベントが発生する． したがって，2 行目にはその時点で街 1 に住むビーバーの数である 13 を出力する．

6 日目は調査イベントが発生する． したがって，3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する．

7 日目以降も同様にイベントが発生するが，ここでは説明を省略する．

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

入力例 3

7
1 2 1 3 3 2
5 2 8 9 4 0 5
10
1 3 1
2 4 10
3 2
1 6 3
1 2 0
3 1
3 4
2 5 6
3 5
3 3

出力例 3

6
18
19
6
0

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

葵は N 枚のカードを持っていて，カードには 1 から N までの番号が付けられている．各カードには 1 つの正の整数が書かれており，カード i (1 \leqq i \leqq N) に書かれた整数は A_i である．

葵はカードと黒板を用いて Q 回の遊びを行う．j 回目 (1 \leqq j \leqq Q) に行う遊びは以下のようなものである．

• 黒板に 0 を書き込む．
• 机にカード L_j, L_j + 1, \dots, R_j をこの順に左から右へ一列に並べる．
• 以下の行動を R_j - L_j + 1 回行う．k 回目 (1 \leqq k \leqq R_j - L_j + 1) の行動は以下のようなものである．
  • 現在黒板に書き込まれている整数を x とし，机に並べたカードの列の中で左から k 番目のカードに書かれている整数を y とする．x を黒板から消し，x + y または x - y を黒板に書き込む．x - y を黒板に書き込んだ場合，ういろう（和菓子）を 1 個食べる．
  • ただし，0 より小さい整数を黒板に書き込むことはできない．

あなたは，それぞれの遊びにおいて葵が食べるういろうの個数としてありうる最大の値を知りたい．

カードと遊びの情報が与えられたとき，それぞれの遊びにおいて葵が食べるういろうの個数としてありうる最大の値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq 100 (1 \leqq i \leqq N)．
• 1 \leqq Q \leqq 200\,000．
• 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (3 点) N \leqq 20，Q \leqq 20．
2. (5 点) N \leqq 300，Q \leqq 20．
3. (7 点) N \leqq 5\,000，Q \leqq 20．
4. (15 点) Q \leqq 20．
5. (21 点) A_i \leqq 2 (1 \leqq i \leqq N)．
6. (29 点) A_i \leqq 20 (1 \leqq i \leqq N)．
7. (20 点) 追加の制約はない．

入力例 1

5
3 4 7 2 8
2
1 3
4 4

出力例 1

1
0

1 回目の遊びでは，以下のような場合が考えられる．

• 最初に，黒板に 0 を書き込む．
• 次に，机にカード 1, 2, 3 をこの順に左から右へ一列に並べる．
• 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 3 である．0 を黒板から消し，3 を黒板に書き込む．
• 現在黒板に書き込まれている整数は 3 で，机に並べたカードの列の中で左から 2 番目のカードに書かれている整数は 4 である．3 を黒板から消し，7 を黒板に書き込む．
• 現在黒板に書き込まれている整数は 7 で，机に並べたカードの列の中で左から 3 番目のカードに書かれている整数は 7 である．7 を黒板から消し，0 を黒板に書き込む．ういろうを 1 個食べる．

このとき，1 回目の遊びで葵が食べるういろうの個数は 1 個である．1 回目の遊びで葵が食べるういろうの個数は 2 個以上にならないことが示せる．したがって，1 を出力する．

2 回目の遊びでは，以下のような場合が考えられる．

• 最初に，黒板に 0 を書き込む．
• 次に，机にカード 4 を並べる．
• 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 2 である．0 を黒板から消し，2 を黒板に書き込む．

このとき，2 回目の遊びで葵が食べるういろうの個数は 0 個である．2 回目の遊びで葵が食べるういろうの個数は 1 個以上にならないことが示せる．したがって，0 を出力する．

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

入力例 2

14
1 2 2 1 2 1 1 2 1 2 2 1 1 1
5
1 2
1 14
5 11
3 12
4 7

出力例 2

0
8
4
6
2

1 回目の遊びでは，以下のような場合が考えられる．

• 最初に，黒板に 0 を書き込む．
• 次に，机にカード 1, 2 をこの順に左から右へ一列に並べる．
• 現在黒板に書き込まれている整数は 0 で，机に並べたカードの列の中で左から 1 番目のカードに書かれている整数は 1 である．0 を黒板から消し，1 を黒板に書き込む．
• 現在黒板に書き込まれている整数は 1 で，机に並べたカードの列の中で左から 2 番目のカードに書かれている整数は 2 である．1 を黒板から消し，3 を黒板に書き込む．

このとき，1 回目の遊びで葵が食べるういろうの個数は 0 個である．1 回目の遊びで葵が食べるういろうの個数は 1 個以上にならないことが示せる．したがって，0 を出力する．

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

入力例 3

8
16 23 45 76 43 97 12 43
7
1 8
3 7
2 7
4 5
5 8
2 6
3 5

出力例 3

3
2
2
1
2
2
1

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