問題文

K 理事長は，役員がいる部屋の室温を調節する役割を担っており，役員ができるだけ快適に過ごせるようにしたいと考えている．

今，部屋に N 人の役員がいる．それぞれの役員には 1 から N までの番号が付けられており，上着を着ていない状態での役員 i (1 \leqq i \leqq N) の適温は A_i 度である． また，それぞれの役員について，上着を 1 枚着るごとに適温が T 度下がる．すなわち，役員 i が上着を k 枚着ると，役員 i の適温は A_i-kT 度になる．

室温を x 度，ある役員の適温を y 度とすると，その役員の不快度は |x-y| で表される．ただし， |t| は t の絶対値を表す．各役員は室温に応じて，不快度が最小となるよう 0 枚以上の適切な枚数の上着を着る．

ここで K 理事長は，役員の不快度の最大値を部屋の不快度と呼ぶことにし，部屋の不快度が最小となるように室温を設定することにした．ただし，設定する室温は整数でなければならない．

役員と適温に関する情報が与えられたとき，部屋の不快度としてありうる最小値を求めるプログラムを作成せよ．

制約

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

小課題

1. (15 点) N = 2．
2. (5 点) N \leqq 3\,000，T = 1．
3. (30 点) N \leqq 3\,000，T \leqq 2．
4. (35 点) N \leqq 3\,000，T \leqq 3\,000．
5. (15 点) 追加の制約はない．

入力例 1

2 4
19 24

出力例 1

1

たとえば，室温を 16 度に設定すると，役員 1 は上着を 1 枚着ることで適温が 15 度になり，役員 1 の不快度は |16 - 15| = 1 となる． 役員 2 は上着を 2 枚着ることで適温が 16 度になり，役員 2 の不快度は |16 - 16| = 0 となる．

このとき，部屋の不快度は 1 となる． また，部屋の不快度を 1 より小さくすることはできないので， 1 を出力する．

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

入力例 2

3 1
21 19 23

出力例 2

0

たとえば，室温を 19 度に設定すると，部屋の不快度は 0 となる．よって 0 を出力する．

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

入力例 3

6 8
24 22 21 25 29 17

出力例 3

2

たとえば，室温を 15 度に設定すると，部屋の不快度は 2 となる．部屋の不快度を 2 より小さくすることはできないので 2 を出力する．

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

問題文

JOI 国には N 個の駅があり，1 から N までの番号が付けられている．また，JOI 国には M 本の鉄道路線があり，1 から M までの番号が付けられている．鉄道路線 i (1 \leqq i \leqq M) は駅 A_i と駅 B_i を双方向に結んでおり，その移動には C_i 分を要する．

JOI 国の大臣であるあなたは，以下のように鉄道路線を新たに 1 本建設することにした．

• 1 \leqq u < v \leqq N を満たす整数 u, v を選ぶ．駅 u と駅 v を双方向に結び，その移動に L 分を要する鉄道路線を JOI 国に建設する．すでに駅 u と駅 v を双方向に結ぶ鉄道路線があってもよいことに注意せよ．

あなたが建設を行った後に，駅 S から駅 T までいくつかの鉄道路線を用いて K 分以内に移動できるようになっている場合，国王は喜ぶ．なお，鉄道路線の乗り換え時間や待ち時間は考えないものとする．

建設する際の 2 つの整数 u, v の選び方は \frac{N \left( N - 1 \right)}{2} 通りあるが，このうち国王が喜ぶような選び方が何通りあるかあなたは知りたい．

駅と鉄道路線，国王の要望の情報が与えられたとき，国王が喜ぶような 2 つの整数の選び方が何通りあるかを求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 200\,000．
• 1 \leqq M \leqq 200\,000．
• 1 \leqq S < T \leqq N．
• 1 \leqq L \leqq 10^{9}．
• 1 \leqq K \leqq 10^{15}．
• 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M)．
• (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M)．
• 1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq M)．
• 入力される値はすべて整数である．

小課題

1. (8 点) L = 1，K = 2，C_i = 1 (1 \leqq i \leqq M)．
2. (16 点) N \leqq 50，M \leqq 50．
3. (29 点) N \leqq 3\,000，M \leqq 3\,000．
4. (47 点) 追加の制約はない．

入力例 1

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

出力例 1

4

たとえば，あなたが u = 3, v = 6 と選んだとする．駅 3 と駅 6 を双方向に結び，その移動に 1 分を要する鉄道路線が JOI 国に建設される．

このとき，以下のようにして，駅 6 から駅 7 まで鉄道路線を用いて 2 分で移動できる．駅 6 から駅 7 まで 2 分以内に移動できるようになっているため，国王は喜ぶ．

1. 駅 3 と駅 6 を双方向に結ぶ路線を用いて，駅 6 から駅 3 に移動する．これには 1 分を要する．
2. 駅 3 と駅 7 を双方向に結ぶ路線を用いて，駅 3 から駅 7 に移動する．これには 1 分を要する．

国王が喜ぶような 2 つの整数の選び方はこの場合を含めて 4 通りある．したがって，4 を出力する．

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

入力例 2

3 2
1 3 1 2
1 2 1
2 3 1       

出力例 2

3

あなたがどのように 2 つの整数を選んでも，国王は喜ぶ．すなわち，国王が喜ぶような 2 つの整数の選び方は 3 通りある．したがって，3 を出力する．

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

入力例 3

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

出力例 3

0

あなたがどのように 2 つの整数を選んでも，国王が喜ぶことはない．したがって，0 を出力する．

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

入力例 4

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645  

出力例 4

16

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

問題文

JOI 街道は東西に伸びる長さ L メートルの道路であり，道路の西端から l メートル (0 \leqq l \leqq L) 進んだ場所は地点 l と呼ばれている．

さて，今年は JOI 街道で初めてマラソン大会が開催されることとなった．このマラソン大会は通常のルールとは異なり，次のようなルールに基づいて行われる．

• 道路上に N 個のボールが置かれており，i 番目 (1 \leqq i \leqq N) のボールは地点 X_i に置かれている．複数のボールが同じ地点に置かれていることもある．
• 参加者は定められたスタート地点から出発する．
• N 個のボールをすべて持った状態で，定められたゴール地点に制限時間内にたどり着くと完走となる．ただし，一度持ったボールを地面に置くと失格となる．

この大会のスタート地点，ゴール地点および制限時間はまだ公開されていないが，Q 個のシナリオのいずれかになることは既に公開されている． j 番目 (1 \leqq j \leqq Q) のシナリオでは，スタート地点が地点 S_j，ゴール地点が地点 G_j，制限時間が T_j 秒である．

マラソン大会の参加者である理恵さんは，ボールを 1 個拾うのに 1 秒かかり，x 個のボールを持った状態で道路上を 1 メートル走るのに x+1 秒かかる．

JOI 街道，ボール，シナリオに関する情報が与えられたとき，それぞれのシナリオについて，理恵さんが完走する方法が存在するかを判定するプログラムを作成せよ．

制約

• 1 \leqq N \leqq 500\,000．
• 1 \leqq L \leqq 500\,000．
• 0 \leqq X_i \leqq L (1 \leqq i \leqq N)．
• 1 \leqq Q \leqq 500\,000．
• 0 \leqq S_j \leqq L (1 \leqq j \leqq Q)．
• 0 \leqq G_j \leqq L (1 \leqq j \leqq Q)．
• 1 \leqq T_j \leqq 500\,000 (1 \leqq j \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (7 点) N \leqq 7，Q \leqq 10，S_j = 0，G_j = 0 (1 \leqq j \leqq Q)．
2. (7 点) N \leqq 7，Q \leqq 10．
3. (10 点) N \leqq 14，Q \leqq 10．
4. (28 点) N \leqq 100，Q \leqq 10．
5. (10 点) N \leqq 2\,000，Q \leqq 10．
6. (19 点) N \leqq 2\,000．
7. (19 点) 追加の制約はない．

入力例 1

3 100
30 80 30
3
0 100 403
0 100 300
0 100 262

出力例 1

Yes
Yes
No

1 番目のシナリオでは，スタート地点は地点 0，ゴール地点は地点 100，制限時間は 403 秒である．以下のようにして，制限時間内の 263 秒で完走することができる．よって，1 行目には Yes を出力する．

2 番目のシナリオでは，スタート地点とゴール地点は 1 番目のシナリオと同じであるが，制限時間は 300 秒となっている．前と同じ方法で，制限時間内の 263 秒で完走することができる．よって，2 行目には Yes を出力する．

3 番目のシナリオでは，スタート地点とゴール地点は 1, 2 番目のシナリオと同じであるが，制限時間は 262 秒となっている．制限時間内に完走する方法は存在しない．よって，3 行目には No を出力する．

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

入力例 2

3 100
30 80 30
3
0 0 403
0 0 300
0 0 262

出力例 2

Yes
No
No

1 番目のシナリオでは，スタート地点は地点 0，ゴール地点は地点 0，制限時間は 403 秒である．以下のようにして，制限時間内の 403 秒で完走することができる．よって，1 行目には Yes を出力する．

2, 3 番目のシナリオでは，スタート地点とゴール地点は 1 番目のシナリオと同じであるが，制限時間はそれぞれ 300 秒，262 秒となっている．どちらについても，制限時間内に完走する方法は存在しない．よって，2 行目には No を，3 行目には No を出力する．

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

入力例 3

6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600

出力例 3

No
Yes
No
Yes

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

問題文

JOI 学園には N 人の生徒がおり，それぞれ 1 から N までの番号が付けられている．

JOI 学園では，近日プレゼント交換会が開催される予定である． 各生徒はそこに持参するためのプレゼントを 1 つずつ用意しており，生徒 i (1\leqq i \leqq N) が持参する予定のプレゼントの価値は A_i である． 生徒たちは自分が持参したプレゼントに比べて価値が低すぎるプレゼントを貰うことを嫌がっており，具体的には，生徒 i は価値 B_i 未満のプレゼントを受け取ると不満を抱く． ここで，B_i < A_i が成り立っている．

ただし，N 人の生徒全員がプレゼント交換会に実際に参加するとは限らない． JOI 学園のトップである K 理事長は，プレゼント交換会に参加する生徒のグループとして Q 個の可能性を検討しており，j 個目 (1\leqq j\leqq Q) のグループは R_j-L_j+1 人の生徒 L_j,L_j+1,\dots,R_j からなる．

ある 2 人以上の生徒のグループについて，誰かが自分の持参したプレゼントを受け取ったり不満を抱いたりすることなくグループ内でプレゼントを交換できるとき，そのグループはプレゼント交換可能であるという． 厳密には，m 人 (m \geqq 2) の生徒 p_1,p_2,\dots,p_m からなるグループがプレゼント交換可能であるとは，p_1,p_2,\dots,p_m を並び替えてできる数列 q_1,q_2,\dots,q_m であって，以下の条件を共に満たすものが存在することをいう． なお，q_k (1\leqq k\leqq m) は生徒 p_k にプレゼントを渡す生徒の番号を表している．

• すべての k (1\leqq k\leqq m) について，p_k \neq q_k．
• すべての k (1\leqq k\leqq m) について，A_{q_k} \geqq B_{p_k}．

プレゼント交換会を成功させたい K 理事長は，Q 個のグループそれぞれについてプレゼント交換可能であるかどうかを調べようとしている．

生徒の情報とグループの情報が与えられたとき，それぞれのグループについてプレゼント交換可能であるかどうかを判定するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 500\,000．
• 1 \leqq B_i < A_i \leqq 2N (1\leqq i\leqq N)．
• A_1,B_1,A_2,B_2,\dots,A_N,B_N はすべて異なる．
• 1 \leqq Q \leqq 200\,000．
• 1 \leqq L_j < R_j \leqq N (1\leqq j\leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (4 点) N \leqq 10，Q \leqq 10．
2. (5 点) N \leqq 18，Q \leqq 10．
3. (10 点) N \leqq 100\,000，A_1 \geqq 2N-2，B_1=1，Q=1，L_1=1，R_1=N．
4. (31 点) N \leqq 100\,000，Q \leqq 10．
5. (8 点) N \leqq 100\,000，A_i < A_{i+1}，B_i < B_{i+1} (1\leqq i\leqq N-1)．
6. (12 点) N \leqq 100\,000，A_i < A_{i+1} (1\leqq i\leqq N-1)．
7. (18 点) N \leqq 100\,000．
8. (12 点) 追加の制約はない．

入力例 1

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

出力例 1

Yes
No
Yes

1 個目のグループは，2 人の生徒 3,4 からなる． 生徒 3 が生徒 4 のプレゼントを，生徒 4 が生徒 3 のプレゼントを受け取った場合，A_3\geqq B_4 かつ A_4\geqq B_3 より，どちらの生徒も不満を抱かない． よって，このグループはプレゼント交換可能であるので，1 行目には Yes を出力する．

2 個目のグループは，3 人の生徒 1,2,3 からなる． A_1 < B_2 かつ A_3 < B_2 より，生徒 2 は生徒 1,3 のいずれのプレゼントを受け取っても不満を抱いてしまう． よって，このグループはプレゼント交換可能でないので，2 行目には No を出力する．

3 個目のグループは，4 人の生徒 1,2,3,4 からなる． たとえば，生徒 1 が生徒 2 のプレゼントを，生徒 2 が生徒 4 のプレゼントを，生徒 3 が生徒 1 のプレゼントを，生徒 4 が生徒 3 のプレゼントを受け取れば誰も不満を抱かない． よって，このグループはプレゼント交換可能であるので，3 行目には Yes を出力する．

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

入力例 2

3
5 6 3
1 4 2
1
1 3

出力例 2

Yes

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

入力例 3

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

出力例 3

No
Yes
No

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

入力例 4

10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
8
2 9
1 6
2 8
2 4
1 2
1 6
7 10
5 8

出力例 4

No
No
Yes
No
No
No
Yes
Yes

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

問題文

JOI 市には，無限に長い H 本の東西方向の道路と W 本の南北方向の道路からなる格子状の道路網がある．北から i 本目 (1 \leqq i \leqq H) の東西方向の道路と，西から j 本目 (1 \leqq j \leqq W) の南北方向の道路が交わる交差点を交差点 (i, j) と呼ぶことにする．

現在，道路の一部は整備不良により通行止めになっている．具体的な通行止めの状況は以下の通りである．

• 北から i 本目 (1 \leqq i \leqq H) の東西方向の道路の，交差点 (i, j) と交差点 (i, j + 1) を繋ぐ部分 (1 \leqq j \leqq W - 1) は，A_{i, j} = 0 のとき通行止めで，A_{i, j} = 1 のとき通行可能である．
• 西から j 本目 (1 \leqq j \leqq W) の南北方向の道路の，交差点 (i, j) と交差点 (i + 1, j) を繋ぐ部分 (1 \leqq i \leqq H - 1) は，B_{i, j} = 0 のとき通行止めで，B_{i, j} = 1 のとき通行可能である．
• 道路のその他の部分，すなわち H \times W 個の交差点の外側の部分はすべて通行止めである．

JOI 市の市長である K 理事長は，この道路網の整備計画を作ることにした．整備計画は，0 回以上の整備からなる． 1 回の整備では，1 \leqq i \leqq H を満たす整数 i を 1 つ選び，以下のことを行う：

1 \leqq j \leqq W - 1 を満たすすべての整数 j について，北から i 本目の東西方向の道路の，交差点 (i, j) と交差点 (i, j + 1) を繋ぐ部分を（もし通行止めであれば）通行可能にする．これには全体で C_i 日間かかる．ただし，C_i は 1 または 2 である．

整備計画に含まれる複数の整備を同時に並行して行うことはできない．したがって，整備計画の実行に必要な日数は，整備計画に含まれるすべての整備にかかる日数の合計である．

K 理事長は，まず市の重要施設の間を行き来できるようにするため，あなたに Q 個の質問をした． k 個目 (1 \leqq k \leqq Q) の質問は以下のようなものである．

T_k 個の交差点 (X_{k, 1}, Y_{k, 1}), (X_{k, 2}, Y_{k, 2}), \dots, (X_{k, T_k}, Y_{k, T_k}) の間を，道路の通行可能な部分のみを通って行き来できるようにするような整備計画は存在するか． 存在するならば，そのような整備計画の実行に必要な日数として考えられる最小値は何日間か．

道路網の通行止めの状況，東西方向の各道路の整備にかかる日数，K 理事長の質問の内容が与えられたとき，K 理事長の質問にすべて答えるプログラムを作成せよ．

制約

• 2 \leqq H．
• 2 \leqq W．
• H \times W \leqq 1\,000\,000．
• 1 \leqq Q \leqq 100\,000．
• A_{i, j} は 0 または 1 (1 \leqq i \leqq H, 1 \leqq j \leqq W - 1)．
• B_{i, j} は 0 または 1 (1 \leqq i \leqq H - 1, 1 \leqq j \leqq W)．
• C_i は 1 または 2 (1 \leqq i \leqq H)．
• 2 \leqq T_k (1 \leqq k \leqq Q)．
• T_1 + T_2 + \cdots + T_Q \leqq 200\,000．
• 1 \leqq X_{k, l} \leqq H (1 \leqq k \leqq Q, 1 \leqq l \leqq T_k)．
• 1 \leqq Y_{k, l} \leqq W (1 \leqq k \leqq Q, 1 \leqq l \leqq T_k)．
• (X_{k, 1}, Y_{k, 1}), (X_{k, 2}, Y_{k, 2}), \dots, (X_{k, T_k}, Y_{k, T_k}) は相異なる (1 \leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (10 点) C_i = 1 (1 \leqq i \leqq H)，Q \leqq 5，T_k = 2 (1 \leqq k \leqq Q)，A_{i, j} = 0 (1 \leqq i \leqq H, 1 \leqq j \leqq W - 1)．
2. (6 点) C_i = 1 (1 \leqq i \leqq H)，Q \leqq 5，T_k = 2 (1 \leqq k \leqq Q)．
3. (15 点) C_i = 1 (1 \leqq i \leqq H)，Q \leqq 5．
4. (11 点) C_i = 1 (1 \leqq i \leqq H)，T_k = 2 (1 \leqq k \leqq Q)．
5. (6 点) C_i = 1 (1 \leqq i \leqq H)．
6. (12 点) Q \leqq 5．
7. (26 点) T_k = 2 (1 \leqq k \leqq Q)．
8. (14 点) 追加の制約はない．

入力例 1

4 3 4
00
00
00
00
100
001
000
1 1 1 1
2
1 1
3 3
2
3 1
1 2
2
2 3
3 3
2
4 2
3 2

出力例 1

1
3
0
-1

以下の図は，現在の通行止めの状況である．灰色は通行止めを表し，青色は通行可能を表している．

• 1 個目の質問では，整数 i として 2 を選ぶような整備を行うと通行止めの状況は下図のようになり，交差点 (1, 1), (3, 3) の間を互いに行き来できるようになる．
  
  この 1 回の整備のみからなる整備計画の実行に必要な日数は 1 であり，これより少ない日数で交差点 (1, 1), (3, 3) の間を互いに行き来できるようにするような整備計画は存在しないため，1 を出力する．
• 2 個目の質問では，整数 i としてそれぞれ 1, 2, 3 を選ぶような 3 回の整備を行うと，交差点 (3, 1), (1, 2) の間を互いに行き来できるようになる． この 3 回の整備からなる整備計画の実行に必要な日数は 3 であり，これより少ない日数で交差点 (3, 1), (1, 2) の間を互いに行き来できるようにするような整備計画は存在しないため，3 を出力する．
• 3 個目の質問では，整備を 1 回も行わなくても交差点 (2, 3), (3, 3) の間を互いに行き来できるので，0 を出力する．
• 4 個目の質問では，交差点 (4, 2), (3, 2) の間を互いに行き来できるようにするような整備計画は存在しないため，-1 を出力する．

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

入力例 2

4 4 4
100
110
011
010
0010
1001
0101
1 1 1 1
2
1 2
3 1
2
1 4
4 1
2
3 2
1 2
2
4 3
1 1

出力例 2

1
3
2
2

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

入力例 3

7 3 3
10
00
00
10
00
01
00
110
101
011
001
110
100
1 1 1 1 1 1 1
3
7 2
3 1
3 2
3
3 1
6 3
2 3
7
2 2
1 3
7 3
5 2
1 2
7 2
3 1

出力例 3

3
2
4

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

入力例 4

4 3 3
00
00
10
00
110
011
001
1 2 2 2
2
1 1
3 1
2
4 3
2 1
2
4 1
1 3

出力例 4

1
2
5

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

入力例 5

7 3 2
01
00
00
00
00
10
01
100
110
011
001
101
001
1 1 2 1 1 2 2
3
7 2
1 3
5 1
5
1 1
2 2
3 1
2 3
4 2

出力例 5

4
1

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