問題文

Paken Olympiad in Informatics(POI)では、番号 1,2,\dots,N からなる N 人の選手が 4 日間からなる競技を行います。番号 i の選手について、j 日目の競技で取った点数は A_{i,j} であることがわかっています。 POI では、以下のルールに従って順位が決められます。

• i 番目の選手のスコアを (10^{100} \times \sum_{j=1}^{4} A_{i,j} \times 2^{j-1}) - i とする。このとき、制約の範囲内で、スコアが同じになる選手が存在しないことが証明できるので、スコアが k 番目に大きい選手を k 位とする。

k=1,2,3,4 について、k 位の選手の番号を求めてください。

制約

• 4 \leq N \leq 30
• 0 \leq A_{i,j} \leq 300
• 入力はすべて整数である。

入力例 1

6
164 134 158 178
200 167 63 173
147 149 154 85
132 111 76 82
69 93 52 126
0 98 83 78

出力例 1

1
2
3
5

入力例 2

4
300 300 300 300
300 300 300 300
300 300 300 300
300 300 300 300

出力例 2

1
2
3
4

全員の点数が全く同じになることも考えられます。

問題文

パ研王国には、パケンアリと呼ばれるアリが生息している。パケンアリは長さ M の細長い巣を作り、この巣は左端を座標 0、右端を座標 M とする数直線として表される。

生物学者のパケン氏は、パケンアリに以下の習性があることを発見した。

• パケンアリは、数直線上を今向いている方向に 1 秒あたり 1 の速さで進む。
• 2 匹のパケンアリがある時刻に同じ座標に到達したとき、2 匹のアリは互いにすれ違うことなく即座に進行方向を反転させる。なお、制約より、3 匹以上のパケンアリが同時に同じ座標に到達することはないことが保証される。
• 各パケンアリは、巣の左端（座標 0）か右端（座標 M）に到達した場合も、即座に進行方向を反転させる。

今、パケン氏は Q 個の問題を考えている。i (1 \leq i \leq Q) 番目の問題では整数 l_i と r_i が与えられ、以下のような内容である。

• 座標 A_{l_i}, A_{l_i+1}, \dots, A_{r_i} にパケンアリを 1 匹ずつ右向きに置く。t 秒後、もともと座標 A_j (l_i \leq j \leq r_i) にいたすべてのアリが、それぞれ同時に座標 B_j にいるような非負整数 t の最小値が存在するか判定し、存在する場合はその最小値を求めよ。

Q 個の問題すべてに対し、解答を求めよ。

制約

• 1 \le N, M, Q \le 4 \times {10}^5
• 0 < A_i < M \ (1 \le i \le N)
• A_i \neq A_j \ (i \neq j)
• 0 \le B_j \le M \ (1 \le j \le N)
• 1 \le l_i \le r_i \le N \ (1 \le i \le Q)
• 入力はすべて整数である。

小課題

1. (4 点) N,M \leq 1000,Q \leq 10
2. (8 点) N \leq 1000,Q \leq 10
3. (26 点) Q \leq 10
4. (30 点) N,M,Q \leq {10}^5,A_i < A_{i+1} \ (1 \leq i < N),B_j \leq B_{j+1} \ (1 \leq j < N)
5. (20 点) N,M,Q \leq {10}^5
6. (12 点) 追加の制約はない

入力例 1

4 20 3
1 4 10 15
5 8 17 18
1 4
1 2
3 4

出力例 1

-1
4
7

1 番目の問題について、すべての i について座標 A_i にいたパケンアリが座標 B_i にいるような最小の t は存在しません。よって、答えは -1 となります。

2 番目の問題について、4 秒後に、座標 1 にいたアリは座標 5 に、座標 4 にいたアリは座標 8 に移動し、条件を満たします。これが最小の t であることが示せるため、答えは 4 となります。

3 番目の問題について、7 秒後に、座標 10 にいたアリは座標 17 に、座標 15 にいたアリは座標 M で進行方向を反転させることによって座標 18 に移動し、条件を満たします。これが最小の t であることが示せるため、答えは 7 となります。

問題文

世界に羽ばたくイラストレーターであるパフィンのパ太郎は、たくさんの依頼にすべて誠実に応えることで有名である。

これからパ太郎のもとに依頼が入る。入る依頼は N 個で、i 番目の依頼は時刻 T_i に入り、その報酬は P_i で、要求される完成度は Q_i である。不思議なことに、P_i はすべて相異なる。

パ太郎は、時刻 1,2,\dots の順に以下の行動を行う。

• まず、その時刻に入った依頼を確認する。はじめ、これらの依頼の進捗は 0 である。
• まだ終わっていない依頼があるなら、そのうち最も報酬が大きい依頼を選び、進捗を 1 増やす。進捗が Q_i と等しくなった依頼は終わる。

スケジュールを練っているうちに、パ太郎は、知り合いであるK運営長が唐突に依頼を入れる可能性に気がついた。パ太郎は X 個のシナリオを考えている。i 番目のシナリオは以下のようなものである。

• K運営長が、時刻 t_i に報酬 p_i 、要求される完成度 q_i の依頼を入れる。不思議なことに、P に p_i は含まれない。

各シナリオについて、K運営長の依頼が終わる時刻を求めるプログラムを作成せよ。

制約

• 1 \leq N \leq 2\times 10^5
• 1\leq T_1\leq T_2\leq \dots \leq T_N\leq 10^{14}
• 1\leq P_i\leq 10^9
• P_i\ne P_j (i\ne j)
• 1\leq Q_i\leq 10^9
• 1\leq X\leq 2\times 10^5
• 1\leq t_i\leq 10^{14}
• 1\leq p_i\leq 10^9
• p_i \ne P_j
• 1\leq q_i\leq 10^9
• 入力はすべて整数

小課題

1. (10 点) X\leq 10
2. (15 点) P_i\gt P_{i+1}
3. (20 点) T_i,t_i\leq 2\times 10^5,\sum_{i=1}^{N}Q_i\leq 2\times 10^5,q_i\leq 2\times 10^5
4. (55 点) 追加の制約はない。

入力例 1

5
1 4 4
1 8 2
2 6 5
3 10 1
4 2 1
3
2 9 2
1 15 10
3 1 1

出力例 1

4
10
14

報酬が p 、要求される完成度が q の依頼を依頼 (p,q) と表す。

1 番目のシナリオでは、パ太郎は以下のように行動する。

• 時刻 1 に、依頼 (4,4),(8,2) が入る。報酬が最も高いのは依頼 (8,2) なので、依頼 (8,2) の進捗を 1 増やす。
• 時刻 2 に、依頼 (6,5),(9,2) が入る。報酬が最も高いのは依頼 (9,2) なので、依頼 (9,2) の進捗を 1 増やす。
• 時刻 3 に、依頼 (10,1) が入る。報酬が最も高いのは依頼 (10,1) なので、依頼 (10,1) の進捗を 1 増やす。進捗が 1 になったので、この依頼は終わる。
• 時刻 4 に、依頼 (2,1) が入る。報酬が最も高いのは依頼 (9,2) なので、依頼 (9,2) の進捗を 1 増やす。進捗が 2 になったので、この依頼は終わる。

K運営長の依頼である依頼 (9,2) は時刻 4 に終わるので、4 を出力せよ。

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

入力例 2

15
19271058196 967824729 152036485
22712438628 910500852 981520310
140039456534 857077284 620411718
250480340689 769431650 298766521
251317817929 744280520 361324668
274195603603 715892722 480968805
344670306080 499774361 297846843
404902144817 419370025 285187325
520643152574 320064892 924193632
521915710072 249168130 628902494
543856067506 245532751 755031424
561032100177 239276621 713892371
710671228979 198319687 722757772
786820954868 164832983 69837030
946667800961 80707350 486834509
15
759622046068 88860862 423817262
86416230707 596982638 272961036
222135105453 623807668 225447688
987307024314 434140395 210989591
284114340148 853214705 836365490
935147463515 366719378 859904884
22078598728 490910900 362117198
519370635632 736444921 422952344
909241707938 29032918 112179585
687828700252 980166390 487330736
588669383658 735908347 528451855
828303497438 455644532 870392056
969530498200 491489928 888795971
436550659389 138264655 343910843
548244874878 118927479 759025737

出力例 2

760045863329
86689191742
222360553140
987518013904
284950705637
936007368398
22440715925
519793587975
909353887522
688316030987
589197835512
829173889493
970419294170
436894570231
549003900614

この入力は小課題 2,4 の制約を満たす。

問題文

パケン王国のパケン雪原に洞窟があり、洞窟には N 個の部屋があります。また、部屋 i には初期状態で大きさ A_i の氷があります。 また、洞窟には部屋と部屋の間を双方向に結ぶ通路が N-1 本あり、i 本目の通路は部屋 u_i と部屋 v_i を結んでいて、c_i=1 のときに限り i 本目の通路に熱源が置かれています。ここで、任意の部屋について、いくつかの通路を通ることで他のすべての部屋に到達できることが保証されます。

時刻 0 から、部屋 i の氷は、以下の条件を満たしているときに限り単位時間あたり 1 の速度で大きさが減少します。ただし、氷の大きさが 0 より小さくなることはないものとします。

• 部屋 i から、大きさが 0 より大きい氷がある他の部屋を通らずに、いずれかの熱源が置かれた通路に到達することができる。

Q 個の質問が与えられるので、それぞれについて解答してください。i 個目の質問は以下のようなものです。

• 部屋 a_i から部屋 b_i まで移動する際、通る通路の本数を最小化するような経路を考える（このような経路は一意に定まることが証明可能である）。このとき、移動の途中で通る部屋すべて（部屋 a_i, b_i にある氷も含める）に対する、時刻 t_i における氷の大きさの和を求めよ。

制約

• 2 \le N \le 200000
• 1 \le Q \le 200000
• 1 \le A_i \le 10^9
• 1 \le u_i, v_i \le N
• u_i \neq v_i
• c_i \in \{0, 1\}
• c_i = 1 となる i が少なくとも 1 つ存在する
• 1 \le a_i, b_i \le N
• 0 \le t_i \le 10^{10}
• 任意の部屋について、いくつかの通路を通ることで他のすべての部屋に到達できる
• 入力はすべて整数である

小課題

1. (7 点) N, Q \leq 1000,u_i = i, v_i = i+1\ (1 \le i \le N-1)
2. (8 点) N, Q \leq 1000
3. (7 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)、すべての 1 \le i, j \le Q について t_i = t_j である。
4. (14 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)、すべての 1 \le i \le Q について、 (a_i, b_i) = (1, N) である。
5. (28 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)
6. (6 点) N, Q \leq 100000、すべての 1 \le i, j \le Q について t_i = t_j である。
7. (15 点) N, Q \leq 100000
8. (15 点) 追加の制約はない。

入力例 1

3
10 20 30
1 2 1
2 3 0
2
1 3 5
2 3 10

出力例 1

50
40

時刻 0 の時点では、部屋 1 と部屋 2 は熱源の置かれた通路に（他の氷がある部屋を通らずに）到達できるため、氷が溶け始めます。部屋 3 は部屋 2 の氷が邪魔をして熱源に到達できないため、まだ氷は溶けません。

• 1 個目の質問は、時刻 5 の状態に関するものです。部屋 1 の氷の大きさは 10 - 5 = 5、部屋 2 の氷の大きさは 20 - 5 = 15 となっています。部屋 3 の氷はまだ溶け始めていないため大きさは 30 です。求めるべき経路上にある部屋は 1, 2, 3 なので、和である 5 + 15 + 30 = 50 が答えとなります。
• 2 個目の質問は、時刻 10 の状態に関するものです。部屋 1 の氷は完全に溶けて大きさが 0 になり、部屋 2 の氷の大きさは 20 - 10 = 10 となっています。求めるべき経路上の部屋は 2, 3 なので、和である 10 + 30 = 40 が答えとなります。

問題文

パケン王国の一角にある建物、グランド・パケンは縦 H 行、横 W 列の長方形の形をしており、内部は 1 \times 1 の正方形の区画に分割されている。上から a 列目、左から b 列目の区画を区画 (a,b) と呼ぶ。グランド・パケンには N 個の出口があり、i 個目の出口は区画 (A_{i},B_{i}) に位置している。

ある晴天の日、グランド・パケンで、火災が発生した。 火災の発生源は M 箇所あり、i 個目の発生源は (C_i,D_i) にある。すべての火災は 時刻 0 に同時に発生する。 火災は単位時間 1 ごとに上下左右に隣接する区画へ広がる。区画 (x,y) が時刻 t に 燃えている とは、ある火災発生源からのマンハッタン距離が t 以下であることをいう。なお、区画は一度燃え始めるとその後も燃え続ける。

救助隊として派遣されたあなたは、建物の中に取り残された人々を助けるため、次の Q 個のクエリに答える必要がある。 i 番目のクエリでは、次の状況を考える。

• 時刻 0 に、人が区画 (X_{i},Y_{i}) にいる。
• 人は単位時間 1 ごとに上下左右に隣接する区画へ移動できる。
• 人は、滞在する全ての時刻に置いて、その区画がまだ燃えていない場合にのみ行動できる。

すなわち、人がある区画に時刻 t に到達するためには、その区画が燃え始める時刻が t より厳密に大きくなければならない。この条件の下で、その人がいずれかの出口のある区画に到達できるかを判定せよ。到達可能であれば Yes、不可能であれば No を出力せよ。

制約

• 1 \le H, W \le 2 \times 10^5
• 1 \le N, M, Q \le 2 \times 10^5
• 1 \le A_i \le H
• 1 \le B_i \le W
• 1 \le C_i \le H
• 1 \le D_i \le W
• 1 \le X_i \le H
• 1 \le Y_i \le W
• 入力は全て整数

小課題

1. (10 点) H \times W \leq 300
2. (20 点) H,W \leq 300
3. (30 点) H,W \leq 2000
4. (40 点) 追加の制約はない

入力例 1

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

出力例 1

No
No
Yes

1,2 つ目のクエリについて、どのような移動を行ったとしても条件を満たして移動することはできません。

3 つ目のクエリについて、人は時刻 0 に (1,5) にいます。時刻 1 に (2,5) に移動することによって、条件を満たして移動することができます。(2,5) は時刻 3 から燃え始めます。

問題文

2 次元平面上に N 個の点 P_1,P_2,\dots,P_N があり、i 番目の点は (X_i, Y_i) にあります。今、あなたは以下の操作を何回でも繰り返し行うことができます。(操作を 1 回も行わないこともできます。)

• 1 以上 N-2 以下の整数 i を選ぶ。そのあと、P_i と P_{i+2} の中点を M として、P_{i+1} を M と対称な点に移動させる。

点 P_1 と点 P_i の距離を D_i とします。この時、i=2,3,\dots,N について、D_i^2 として考えられる最大値を求めてください。

制約

• 3 \le N \le 2000
• - 2 \times {10}^5 \le X_i, Y_i \le 2 \times {10}^5
• P_{i} \neq P_{i+1} \ (1 \leq i \leq N-1)
• 入力はすべて整数である。

小課題

1. (2 点) N = 3
2. (3 点) N \leq 7
3. (15 点) N \leq 20
4. (15 点) N \leq 40,-40 \leq X_i,Y_i \leq 40
5. (35 点) N \leq 200
6. (30 点) 追加の制約はない

入力例 1

3
0 0
1 1
2 0

出力例 1

2
4

i=1 として操作を行うことを考えます。点 P_1 と点 P_3 の中点は (1,0) となります。よって、点 P_2 は (1,-1) に移動します。この時、{D_2}^2 = 2,{D_3}^2 = 4 となります。

入力例 2

4
0 0
1 0
0 1
1 1

出力例 2

2
4
2

問題文

至高の団子職人であるパグのパ太郎は、N 個の団子を用意し、左から右に一列に並べた。左から i 番目の団子は大きさ c_i で、おいしさは d_i である。

今から、パ太郎は左から 1 個以上 K 個以下の団子を選び、それを並び替えて好きな順番で刺して串団子を作る、という操作を N 個の団子がすべていずれかの串に刺されるまで繰り返す。具体的には、現在残っている団子の番号を u,u+1,\dots,N としたとき、1 以上 \min(N-u+1,K) 以下の整数 s を選び、団子 u,u+1,\dots,u+s-1 を取り出した後、自由な順番で並び替えて串団子を作るという操作を繰り返す。このとき、パ太郎は非常にこだわりが強いので、串団子について以下の条件を満たしている必要がある。

• 串団子に刺された団子の数を t、串団子に刺された団子の大きさとおいしさをそれぞれ順に C_1,C_2,\dots,C_t,D_1,D_2,\dots,D_t としたとき、以下の条件のうち少なくとも一つを満たしている必要がある。

  • k=1,2,\dots,t-1 に対して、k が奇数ならば C_k < C_{k+1} が、k が偶数ならば C_k > C_{k+1} が成り立つ。
  • k=1,2,\dots,t-1 に対して、k が偶数ならば C_k < C_{k+1} が、k が奇数ならば C_k > C_{k+1} が成り立つ。
  • t=1 である。

このとき、この串団子のおいしさを (D_1+D_2+\dots+D_t)^2 で定義する。

操作が終了した後の串団子のおいしさの和として考えられる最大の値を求めよ。

制約

• 1 \le N \le 4000
• 1 \le K \le N
• 0 \le c_i,d_i \le 2 \times {10}^5
• 入力はすべて整数である。

小課題

1. (5 点) N \leq 6
2. (5 点) N \leq 15
3. (11 点) N \leq 300,c_i \leq 2
4. (10 点) c_i \leq 2
5. (23 点) N \leq 300
6. (11 点) c_i \leq 10
7. (35 点) 追加の制約はない

入力例 1

4 3
1 2 1 2
10 20 30 40

出力例 1

8200

例えば、団子 1 だけを使って串団子を、団子 4,3,2 をこの順に使って串団子をこの順に作る場合を考えると、前者の串団子のおいしさは 10^2=100、後者の串団子のおいしさは (40+30+20)^2=90^2=8100 となり、合計で 8200 となる。 団子 1 で串団子を作った後団子 4,2,3 の順で団子を使い串団子を使った場合、問題文中の条件を満たさないため、このような串団子の作り方は考慮しないことに注意せよ。また、例えば団子 1,3 を使って串団子を使うことは不可能であることに注意せよ。

問題文

この問題はインタラクティブな問題である。

パ研洋に N 個の島が浮かんでおり、1,2,\dots,N と番号がつけられている。

また島同士を結ぶ N-1 個の橋があり、i 番目の橋は島 U_i と島 V_i を結んでいる。ここで、どの島からどの島へも橋を何回か渡ることでたどり着くことができる。

K運営長は、これらの島をすべて自身の支配下に置こうとしているが、橋の構造を知らない。そこで、橋の構造を知っているパンサーカメレオンのパ太郎に以下の質問を繰り返すことで、橋の構造を特定することにした。

1. K運営長が、島を 1 個以上 N 個以下選び、パ太郎に伝える。
2. パ太郎は、以下の条件を満たすように N 個の島のうちいくつか沈めるとき、最大で何個の島を沈めずに残せるかをK運営長に伝える。
   • 沈んでいない島はすべてK運営長によって選ばれた島である。
   • どの沈んでいない島からどの沈んでいない島へも橋を何回か渡ることでたどり着くことができる。
   • 沈んでいない島すべてについて、隣接する沈んでいない島は高々 2 つである。

なお、これはパ太郎の思考実験であるため、実際に島を沈めることはない。

パ太郎も暇ではないので、L 回までしかこの質問に答えてくれない。

パ研洋に浮かぶ島の数とパ太郎に質問できる回数が与えられたとき、どの島とどの島を結ぶ橋があるのかを求めるK運営長の戦略を実装せよ。

制約

• N = 256
• 1 \leq U_i,V_i\leq N (1\leq i\leq N-1)
• どの島からどの島へも橋を何回か渡ることでたどり着くことができる。

小課題

1. (5 点) L=33000
2. (25 点) L=10000
3. (20 点) L=6400
4. (50 点) L=4600

入出力

最初に、N,L が標準入力から与えられる。

N L

次に、あなたはパ太郎に L 回以下の質問を行う。選んだ島を島 s_1,s_2,\dots,s_n とするとき、以下の形式で出力せよ。

? n s_1 s_2 \dots s_n

質問すると、パ太郎からの返答が X が標準入力から与えられる。

X

ここで、X は整数で、

• X\ne -1 のとき、質問に対する答えが X であることを表す。
• X=-1 のとき、質問した回数が L 回を超えたか、質問が形式に沿っていないことを表す。
  • このとき、プログラムはすでに不正解と判定されている。ただちにプログラムを終了せよ。

橋の構造を特定することができたら、以下の形式で出力せよ。これは質問回数には計上されない。

! u_1 v_1 u_2 v_2 \dots u_{N-1} v_{N-1}

ここで、各 i について島 u_i と島 v_i を結ぶ橋がある必要がある。また、同じ橋を複数回答えてはならない。この出力の後、ただちにプログラムを終了せよ。

上記のいずれの形式にも当てはまらない出力をした場合、-1 が入力から与えられる。

-1

このときも、プログラムはすでに不正解と判定されている。ただちにプログラムを終了せよ。

注意点

• 出力を行うたびに、末尾に改行を入れて標準出力をflushせよ。そうしなかった場合、ジャッジ結果が TLE となる可能性がある。
• 解答を出力したとき、または -1 を標準入力から受け取ったとき、ただちにプログラムを終了せよ。そうしなかった場合の判定結果は不定である。
• 余計な改行は不正なフォーマットの出力とみなされることに注意せよ。
• この問題のジャッジシステムは適応的（adaptive）でない。 つまり、U と V はジャッジとの対話前に決定され、いかなるタイミングでも変更されることはない。

入出力例

N=5,U=(1,2,2,2),V=(2,3,4,5),L=10 のときの対話の一例を示す。

これは対話の一例であることに注意せよ。特に、これまでの質問とその解答で橋の構造を確実に特定できるとは限らない。

なお、このケースは制約を満たさないため、実際の採点用テストケースには含まれないことに注意せよ。