問題文

JOI 君は，紙とマスキングテープを使い，色塗りをして遊んでいる．

紙は長方形であり，縦 H 行，横 W 列のマス目が描かれている．上から i 行目 (1 \leqq i \leqq H)，左から j 列目 (1 \leqq j \leqq W) のマスをマス (i, j) と呼ぶ．

それぞれのマスには色が 1 つ定められている．色は整数で表され，はじめすべてのマスの色は 0 である．

JOI 君は，この紙とマスキングテープを用いて Q 回の操作を行う． k 回目 (1 \leqq k \leqq Q) の操作は，整数 q_k の値に応じて以下のように説明される．

• q_k = 1 のとき，この操作は整数 x_k, y_k, c_k で表される．マス (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1) それぞれについて，マスがマスキングテープで覆われていなければ，そのマスの色を c_k に変更する．マスがマスキングテープで覆われているならば，そのマスには何もしない．
• q_k = 2 のとき，この操作は整数 x_k, y_k で表される．マス (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1) をマスキングテープで覆う．

Q 回の操作が終わった後，すべてのマスキングテープを剥がす．なお，あるマスのマスキングテープを剥がしたとき，そのマスの色はマスキングテープで覆われる直前の色と同じになる．

Q 回の操作の情報が与えられたとき，最終的な紙のすべてのマスの色を求めるプログラムを作成せよ．

制約

• 2 \leqq H \leqq 500．
• 2 \leqq W \leqq 500．
• 1 \leqq Q \leqq 200 \: 000．
• q_k は 1 か 2 のいずれかである (1 \leqq k \leqq Q)．
• q_k = 1 のとき，1 \leqq x_k \leqq H - 1，1 \leqq y_k \leqq W - 1，1 \leqq c_k \leqq 10^9 (1 \leqq k \leqq Q)．
• q_k = 2 のとき，1 \leqq x_k \leqq H - 1，1 \leqq y_k \leqq W - 1 (1 \leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (32 点) H = 2，W = 2，q_k = 1 (1 \leqq k \leqq Q)．
2. (32 点) q_k = 1 (1 \leqq k \leqq Q)．
3. (36 点) 追加の制約はない．

入力例 1

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

出力例 1

0 0 0 5 0
0 1 1 5 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

4 回の操作を順に見ていく．

1 回目の操作について，q_1 = 1 である．マス (2, 2)，(2, 3)，(3, 2)，(3, 3) はすべてマスキングテープで覆われていないので，色を 1 に変更する．

このとき，紙は以下のようになっている．

0  0  0  0  0
0  1  1  0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

2 回目の操作について，q_2 = 2 である．マス (1, 2)，(1, 3)，(2, 2)，(2, 3) をマスキングテープで覆う．

このとき，紙は以下のようになっている．なお，マスキングテープで覆ったマスの色を表す整数の右に * を付けた．

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

3 回目の操作について，q_3 = 2 である．マス (3, 3)，(3, 4)，(4, 3)，(4, 4) をマスキングテープで覆う．

このとき，紙は以下のようになっている．

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

4 回目の操作について，q_4 = 1 である．マス (1, 4)，(2, 4) はマスキングテープで覆われていないので，色を 5 に変更する．マス (1, 3)，(2, 3) はマスキングテープで覆われているので，何もしない．

このとき，紙は以下のようになっている．

0  0* 0* 5  0
0  1* 1* 5  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

したがって，最終的な紙のすべてのマスの色は出力例のようになっている．

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

入力例 2

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

出力例 2

2 2 0 0 0
2 2 0 2 2
0 0 3 2 2
0 0 3 3 0
0 0 0 0 0

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

入力例 3

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

出力例 3

0 0 0 0 0 0 0 0 0 0
0 0 3 2 2 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 1 1 2
0 1 1 0 0 0 0 0 2 2

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

問題文

ビ太郎はビリヤードで遊んでいる． JOI 国のビリヤードは台上に並べられた N 個のボール 1,2,...,N を用いる遊びであり，台にはボールを落とすための穴が設けられている． 一度穴に落ちたボールは台上には戻さず，そのボールを再び落とすことはできない．ビ太郎の目的は，なるべく大きい番号の書かれたボールを穴に落とすことである．

ボールを落とすのは集中を必要とする作業である． はじめ，ビ太郎の 集中力 は X であり，ボール i (1 \leqq i \leqq N) を落とすと集中力が A_i 減少する．集中力が A_i 未満であるとき，ボール i を落とすことはできない．

また，このビリヤードではボールを落とす順番に関するルールが存在する．具体的には， P_i = -1 (1 \leqq i \leqq N) のとき，ボール i はいつでも落とすことができ， P_i \neq -1 のとき，ボール i を落とすためには，ボール P_i がすでに落とされている必要がある．

ビ太郎が持つ集中力と各ボールの情報が与えられたとき，ビ太郎がボールを穴に落とすことができるか判定し，ボールを落とすことができる場合は落とせるボールの番号の最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 1 \leqq X \leqq 10^{15}．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq P_i \leqq N または P_i = -1 (1 \leqq i \leqq N)．
• P_i \neq i (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (6 点) N \leqq 1000， P_i = -1 (1 \leqq i \leqq N)．
2. (9 点) N \leqq 1000， P_1 = -1， P_i = i-1 (2 \leqq i \leqq N)．
3. (16 点) N \leqq 1000， P_i < i (1 \leqq i \leqq N)．
4. (20 点) P_i < i (1 \leqq i \leqq N)．
5. (19 点) N \leqq 1000．
6. (30 点) 追加の制約はない．

入力例 1

6 7
1 2 4 3 10 100
-1 -1 -1 -1 -1 -1

出力例 1

4

はじめ，ビ太郎の集中力は 7 である．
すべての i (1 \leqq i \leqq N) について P_i = -1 なので，ビ太郎は集中力が足りる限り，すべでのボールをいつでも穴に落とすことができる．

例えば，以下のようにすると，ビ太郎はボール 4 を落とすことができる．

• まず，ボール 3 を穴に落とす．ビ太郎の集中力が 4 減少し，残りの集中力は 3 となる．
• 次に，ボール 4 を穴に落とす．ビ太郎の集中力が 3 減少し，残りの集中力は 0 となる．

また，ビ太郎がボール 5,6 を穴に落とすことはできない．よって，ビ太郎が穴に落とすことのできるボールの番号の最大値は 4 である．

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

入力例 2

5 12
1 2 3 5 8
-1 1 2 3 4

出力例 2

4

はじめ，ビ太郎の集中力は 12 である．
例えば，以下のようにすると，ビ太郎はボール 4 を落とすことができる．

• まず，ボール 1 を穴に落とす． ( P_1 = -1 なので，ボール 1 はいつでも落とすことができる．)
  • ビ太郎の集中力が 1 減少し，残りの集中力は 11 となる．
• 次に，ボール 2 を穴に落とす． ( P_2 = 1 でありボール 1 はすでに落とされているので，ボール 2 を落とすことができる．)
  • ビ太郎の集中力が 2 減少し，残りの集中力は 9 となる．
• 次に，ボール 3 を穴に落とす． ( P_3 = 2 でありボール 2 はすでに落とされているので，ボール 3 を落とすことができる．)
  • ビ太郎の集中力が 3 減少し，残りの集中力は 6 となる．
• 次に，ボール 4 を穴に落とす． ( P_4 = 3 でありボール 3 はすでに落とされているので，ボール 4 を落とすことができる．)
  • ビ太郎の集中力が 5 減少し，残りの集中力は 1 となる．

また，ビ太郎がボール 5 を穴に落とすことはできない．よって，ビ太郎が穴に落とすことのできるボールの番号の最大値は 4 である．

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

入力例 3

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

出力例 3

7

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

入力例 4

2 1000000000000000
1 1
2 1

出力例 4

-1

P_1 = 2 なので，ボール 1 を落とすためには，ボール 2 がすでに落とされている必要がある．逆に， P_2 = 1 なので，ボール 2 を落とすためには，ボール 1 がすでに落とされている必要がある．このことから，ビ太郎は 1 個もボールを落とすことができない．よって， -1 を出力する．

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

入力例 5

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

出力例 5

6

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

問題文

Alice と Bob はソフトクリーム屋さん JOICE に来ている．この店では，客がフレーバー・コーン・トッピングをそれぞれひとつずつ選ぶことによって，ソフトクリームを注文する．

• フレーバーは X 種類あり，値段はそれぞれ A_1, A_2, \dots, A_X である．
• コーンは Y 種類あり，値段はそれぞれ B_1, B_2, \dots, B_Y である．
• トッピングは Z 種類あり，値段はそれぞれ C_1, C_2, \dots, C_Z である．

ソフトクリームの値段は選んだフレーバー・コーン・トッピングの値段の合計となる．ここで，与えられた整数 P に対して，ソフトクリームの スコア をその値段と P との差の絶対値とする．

Alice と Bob は 2 人で 1 つのソフトクリームを注文しようとしているが，2 人がどんなソフトクリームを注文したいかは真逆である．具体的には，Alice はスコアを最大化することを，Bob はスコアを最小化することを目的としている．そこで，以下の方法で，注文するソフトクリームのフレーバー・コーン・トッピングを選ぶことにした．

1. 最初に，Alice がフレーバーを選ぶ．
2. 次に，Bob がコーンを選ぶ．
3. 最後に，Alice がトッピングを選ぶ．

フレーバー，コーン，トッピングに関する情報および整数 P が与えられたとき，両者が各選択で最善を尽くした場合に最終的に注文するソフトクリームのスコアを求めるプログラムを作成せよ．

制約

• 1 \leqq X \leqq 200\,000．
• 1 \leqq Y \leqq 200\,000．
• 1 \leqq Z \leqq 200\,000．
• 0 \leqq P \leqq 3 \times 10^8．
• 0 \leqq A_i \leqq 10^8 (1\leqq i \leqq X)．
• 0 \leqq B_j \leqq 10^8 (1\leqq j \leqq Y)．
• 0 \leqq C_k \leqq 10^8 (1\leqq k \leqq Z)．
• 入力される値はすべて整数である．

小課題

1. (7 点) X = 1， Y = 1， Z \leqq 100．
2. (17 点) X = 1， Y \leqq 100， Z \leqq 100．
3. (21 点) X \leqq 100， Y \leqq 100， Z \leqq 100．
4. (22 点) X \leqq 4\,000， Y \leqq 4\,000， Z \leqq 4\,000．
5. (33 点) 追加の制約はない．

入力例 1

1 1 3 22
5
10
9 2 3

出力例 1

5

フレーバー・コーン・トッピングの選び方は以下の 3 通りある．

• 値段がそれぞれ 5,10,9：値段は合計 24 になるので，スコアは 24 と 22 との差の絶対値である 2
• 値段がそれぞれ 5,10,2：値段は合計 17 になるので，スコアは 17 と 22 との差の絶対値である 5
• 値段がそれぞれ 5,10,3：値段は合計 18 になるので，スコアは 18 と 22 との差の絶対値である 4

まず Alice は値段 5 のフレーバーを選び，次に Bob は値段 10 のコーンを選ぶ．

最後に，Alice はスコアを最大化したいので，値段 2 のトッピングを選んでスコアを 5 にするのが最善である．

よって，両者が最善を尽くした場合のスコアは 5 になる．

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

入力例 2

1 2 2 100
11
33 44
40 60

出力例 2

15

フレーバー・コーン・トッピングの選び方は以下の 4 通りある．

• 値段がそれぞれ 11,33,40：値段は合計 84 になるので，スコアは 84 と 100 との差の絶対値である 16
• 値段がそれぞれ 11,33,60：値段は合計 104 になるので，スコアは 104 と 100 との差の絶対値である 4
• 値段がそれぞれ 11,44,40：値段は合計 95 になるので，スコアは 95 と 100 との差の絶対値である 5
• 値段がそれぞれ 11,44,60：値段は合計 115 になるので，スコアは 115 と 100 との差の絶対値である 15

まず Alice は値段 11 のフレーバーを選ぶ．

次に Bob は値段 33 のコーンと値段 44 のコーンのうちいずれかを選ぶ． ここで Bob が選んだコーンに応じて，Alice はその後スコアを最大化するために以下のような行動をとる．

• Bob が値段 33 のコーンを選んだ場合：Alice は値段 40 のトッピングを選び，スコアを 16 にする．
• Bob が値段 44 のコーンを選んだ場合：Alice は値段 60 のトッピングを選び，スコアを 15 にする．

Bob はスコアを最小化したいので，値段 44 のコーンを選んでスコアを 15 にするのが最善である．

よって，両者が最善を尽くした場合のスコアは 15 になる．

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

入力例 3

2 2 2 0
15 23
5 16
23 45

出力例 3

73

P=0 のとき，スコアは単に選んだフレーバー・コーン・トッピングの値段の合計となるので，Alice はより値段の高いフレーバー・トッピングを選び，Bob はより値段の低いコーンを選ぶのが最善である．

よって，選ぶフレーバー・コーン・トッピングの値段はそれぞれ 23,5,45 であり，スコアは 73 になる．

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

入力例 4

3 3 3 50
12 5 5
2 19 37
10 5 15

出力例 4

14

同じ値段のフレーバーやコーン，トッピングが存在する場合もある事に注意せよ．

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

問題文

あるボリビア料理レストランでは 1 から N までの番号が付けられている N 人のシェフが働いている．シェフ i (1 \leqq i \leqq N) は美味しさが A_i であるシルパンチョと美味しさが B_i であるピケマチョを作ることができる．

ただし，シェフはこだわりが強いため仲が悪い 2 人組が M 組いる．仲が悪い 2 人組の j 番目 (1 \leqq j \leqq M) はシェフ U_j とシェフ V_j の 2 人組である．

このレストランに来店する客は以下のようにして料理を食べる．

• 1 \leqq p < q \leqq N を満たす整数 p, q を選び，シェフ p とシェフ q の 2 人組に料理を作ることを依頼する．ただし，仲が悪い 2 人組に料理を作ることを依頼することはできない．
• シルパンチョとピケマチョの各料理はシェフ p とシェフ q のうち美味しさがより高いものを作ることができるシェフが作る．ある料理について 2 人が同じ美味しさの料理を作ることができるとき，どちらか 1 人のシェフが作る．1 人のシェフが 2 つの料理を作ることも可能であることに注意せよ．
• 客の満足度はシルパンチョの美味しさとピケマチョの美味しさの合計である．

このレストランに 1 から Q までの番号が付けられている Q 人の客が来店した．

客 k (1 \leqq k \leqq Q) は，料理を作ることを依頼することができる 2 人組のうち，満足度が X_k 番目に高くなる 2 人組に料理を作ることを依頼した．具体的には満足度を S として，S \times N^2 + p \times N + q が X_k 番目に高くなるシェフ p とシェフ q (1 \leqq p < q \leqq N) の 2 人組に料理を作ることを依頼した．

レストランのシェフと客の情報が与えられたとき，客 k (1 \leqq k \leqq Q) の満足度を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 400\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N)．
• 0 \leqq M \leqq 400\,000．
• M < \frac{N(N - 1)}{2}．
• 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M)．
• (U_i, V_i) \neq (U_j, V_j) (1 \leqq i < j \leqq M)．
• 1 \leqq Q \leqq 400\,000．
• 1 \leqq X_k \leqq 400\,000 (1 \leqq k \leqq Q)．
• X_k \leqq \frac{N(N - 1)}{2} - M (1 \leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (4 点) N \leqq 50，M \leqq 50，Q \leqq 50，X_k \leqq 50 (1 \leqq k \leqq Q)．
2. (9 点) B_i = 1 (1 \leqq i \leqq N)，M = 0，Q = 1．
3. (10 点) B_i = 1 (1 \leqq i \leqq N)，Q = 1．
4. (5 点) B_i = 1 (1 \leqq i \leqq N)．
5. (29 点) N \leqq 100\,000，M \leqq 100\,000，Q = 1，X_1 = 1．
6. (14 点) N \leqq 100\,000，M \leqq 100\,000，Q = 1，X_1 \leqq 100\,000．
7. (18 点) N \leqq 100\,000，M \leqq 100\,000，Q \leqq 100\,000，X_k \leqq 100\,000 (1 \leqq k \leqq Q)．
8. (11 点) 追加の制約はない．

入力例 1

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

出力例 1

13
13
11
11

料理を作ることを依頼することができるシェフの 2 人組は 4 通りあり，それぞれにおける客の満足度は以下のようになる．

• シェフ 1 とシェフ 2 を選んだとき，シルパンチョはシェフ 2 が作り，ピケマチョはシェフ 1 が作る．したがって，シルパンチョの美味しさは 7 となり，ピケマチョの美味しさは 4 となる．よって，客の満足度は 7 + 4 = 11 である．
• シェフ 1 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 8 となる．よって，客の満足度は 5 + 8 = 13 である．
• シェフ 2 とシェフ 3 を選んだとき，シルパンチョはシェフ 2 が作り，ピケマチョはシェフ 3 が作る．したがって，シルパンチョの美味しさは 7 となり，ピケマチョの美味しさは 4 となる．よって，客の満足度は 7 + 4 = 11 である．
• シェフ 3 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 8 となる．よって，客の満足度は 5 + 8 = 13 である．

したがって，それぞれの客について以下のことが分かる．

• 客 1 はシェフ 3 とシェフ 4 の 2 人組を選んだ．したがって，客 1 の満足度は 13 となった．
• 客 2 はシェフ 1 とシェフ 4 の 2 人組を選んだ．したがって，客 2 の満足度は 13 となった．
• 客 3 はシェフ 2 とシェフ 3 の 2 人組を選んだ．したがって，客 3 の満足度は 11 となった．
• 客 4 はシェフ 1 とシェフ 2 の 2 人組を選んだ．したがって，客 4 の満足度は 11 となった．

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

入力例 2

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

出力例 2

6

料理を作ることを依頼することができるシェフの 2 人組は 3 通りあり，それぞれにおける客の満足度は以下のようになる．

• シェフ 1 とシェフ 3 を選んだとき，シルパンチョはシェフ 3 が作り，ピケマチョはシェフ 1 かシェフ 3 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 5 + 1 = 6 である．
• シェフ 1 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 1 かシェフ 4 が作る．したがって，シルパンチョの美味しさは 4 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 4 + 1 = 5 である．
• シェフ 3 とシェフ 4 を選んだとき，シルパンチョはシェフ 3 が作り，ピケマチョはシェフ 3 かシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 5 + 1 = 6 である．

したがって，客 1 について以下のことが分かる．

• 客 1 はシェフ 3 とシェフ 4 の 2 人組を選んだ．したがって，客 1 の満足度は 6 となった．

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

入力例 3

5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1

出力例 3

9
7
7
10

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

入力例 4

13 12 10
2 28 28 60 48 77 63 92 13 71 36 91 87
85 7 64 15 55 92 66 91 83 35 49 22 61
2 9
8 13
7 11
9 11
8 12
5 12
4 7
11 12
10 12
4 11
1 5
3 8
49 21 46 13 20 41 6 33 24 7

出力例 4

121
169
129
174
169
137
183
148
169
183

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

問題文

ビ太郎は，大きな円形の湖の周りに住んでいる．湖の周りの長さは L であり，湖の周りのある地点にはビ太郎の家がある．ビ太郎の家から湖の周りを時計回りに x (0 \leqq x < L) 移動した地点を地点 x と呼ぶ．現在，湖の周りで行われるマラソン大会が企画されている．

ビ太郎はマラソン大会は以下のように行われる予定であることを聞いた．

• 0 から L - 1 までの番号が付けられたゼッケンが 1 枚ずつ用意されている．マラソン大会の参加者はいずれかのゼッケンを着用する．ゼッケン l (0 \leqq l \leqq L - 1) を着用する参加者のスタート地点は地点 l となる．
• マラソン大会がスタートした後，T ビョウにわたり，参加者はそれぞれの速度で湖の周りを時計回りに移動する．マラソン大会がスタートしてから，t ビョウ (0 \leqq t \leqq T) 経った時点を時刻 t と呼ぶ．

ビ太郎はマラソン大会の参加者名簿を持っている．現在は N 人の参加者が参加者名簿に記載されていて，i 番目の参加者 (1 \leqq i \leqq N) はゼッケン A_i を着用し，1 ビョウあたり S_i の速度で湖の周りを時計回りに移動する予定である．

参加者名簿を元に，ビ太郎はマラソン大会中に起こる衝突の回数を求めた．ここで，衝突とは異なる参加者 2 人が同じ地点にいることを指すものとする．厳密には，0 \leqq p < q \leqq L - 1 を満たす整数 p, q と 0 \leqq t \leqq T を満たす実数 t からなる組 (p, q, t) で，以下の条件を満たすものの個数を求めた．

• ゼッケン p を着用した参加者がいる．
• ゼッケン q を着用した参加者がいる．
• ゼッケン p を着用した参加者とゼッケン q を着用した参加者が，時刻 t に同じ地点にいる．

しかし，その後参加者名簿に Q 回の変更が行われた．j 番目 (1 \leqq j \leqq Q) の変更は 2 つの整数 X_j, Y_j で表され，以下のようなものである．

• 現在，ゼッケン X_j を着用し，1 ビョウあたり Y_j の速度で湖の周りを時計回りに移動する人が参加者名簿に記載されている場合，その人を参加者名簿から削除する．そうでない場合，ゼッケン X_j を着用し，1 ビョウあたり Y_j の速度で湖の周りを時計回りに移動する人を新たに参加者名簿に追加する．

ただし，いずれの変更が終了した時点でも，参加者名簿に記載されている参加者は 2 人以上おり，かつ参加者の着用するゼッケンは相異なることが保証される．

ビ太郎はそれぞれの変更が終了した時点での参加者における，マラソン大会中に起こる衝突の回数を知りたい．問題文の制約より，マラソン大会中に起こる衝突の回数は有限であることが証明できる．

マラソン大会と参加者名簿への変更の情報が与えられたとき，それぞれの変更が終了した時点での参加者における，マラソン大会中に起こる衝突の回数を 1\,000\,000\,007 で割ったあまりを求めるプログラムを作成せよ．

制約

• 2 \leqq N．
• N \leqq L \leqq 10^9．
• 1 \leqq T \leqq 10^9．
• 0 \leqq A_i \leqq L - 1 (1 \leqq i \leqq N)．
• A_i \neq A_j (1 \leqq i < j \leqq N)．
• 1 \leqq S_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq Q．
• N + Q \leqq 100\,000．
• 0 \leqq X_j \leqq L - 1 (1 \leqq j \leqq Q)．
• 1 \leqq Y_j \leqq 10^9 (1 \leqq j \leqq Q)．
• いずれの変更が終了した時点でも，参加者は 2 人以上いる．
• いずれの変更が終了した時点でも，参加者のスタート地点は相異なる．
• 入力される値はすべて整数である．

小課題

1. (10 点) T = 1，S_i \leqq 2 (1 \leqq i \leqq N)，Y_j \leqq 2 (1 \leqq j \leqq Q)．
2. (8 点) N \leqq 2\,000，Q = 1．
3. (11 点) N \leqq 2\,000，Q \leqq 2\,000．
4. (27 点) Q = 1．
5. (34 点) N + Q \leqq 78\,000．
6. (10 点) 追加の制約はない．

入力例 1

3 7 2
1 6 3
4 1 6
1
4 2

出力例 1

7

1 番目の変更が終了した時点での参加者は 4 人である．それぞれの参加者についての情報は以下のようになる．

1. ゼッケン 1 を着用し，地点 1 からスタートする．1 ビョウあたり 4 の速度で時計回りに移動する．
2. ゼッケン 6 を着用し，地点 6 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
3. ゼッケン 3 を着用し，地点 3 からスタートする．1 ビョウあたり 6 の速度で時計回りに移動する．
4. ゼッケン 4 を着用し，地点 4 からスタートする．1 ビョウあたり 2 の速度で時計回りに移動する．

1 番目の変更が終了した時点での参加者におけるマラソン大会中の衝突は以下の 7 回となる．

1. 時刻 \frac{1}{4} に，ゼッケン 3 を着用した参加者とゼッケン 4 を着用した参加者が同じ地点 \frac{9}{2} にいる．
2. 時刻 \frac{3}{5} に，ゼッケン 3 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 \frac{33}{5} にいる．
3. 時刻 \frac{3}{2} に，ゼッケン 1 を着用した参加者とゼッケン 4 を着用した参加者が同じ地点 0 にいる．
4. 時刻 \frac{5}{3} に，ゼッケン 1 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 \frac{2}{3} にいる．
5. 時刻 2 に，ゼッケン 3 を着用した参加者とゼッケン 4 を着用した参加者が同じ地点 1 にいる．
6. 時刻 2 に，ゼッケン 3 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 1 にいる．
7. 時刻 2 に，ゼッケン 4 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 1 にいる．

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

入力例 2

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

出力例 2

1
0

1 番目の変更が終了した時点での参加者は 4 人である．それぞれの参加者についての情報は以下のようになる．

1. ゼッケン 1 を着用し，地点 1 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
2. ゼッケン 3 を着用し，地点 3 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
3. ゼッケン 4 を着用し，地点 4 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
4. ゼッケン 0 を着用し，地点 0 からスタートする．1 ビョウあたり 2 の速度で時計回りに移動する．

1 番目の変更が終了した時点での参加者におけるマラソン大会中の衝突は以下の 1 回となる．

1. 時刻 1 に，ゼッケン 0 を着用した参加者とゼッケン 1 を着用した参加者が同じ地点 2 にいる．

2 番目の変更が終了した時点での参加者は 3 人である．それぞれの参加者についての情報は以下のようになる．

1. ゼッケン 3 を着用し，地点 3 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
2. ゼッケン 4 を着用し，地点 4 からスタートする．1 ビョウあたり 1 の速度で時計回りに移動する．
3. ゼッケン 0 を着用し，地点 0 からスタートする．1 ビョウあたり 2 の速度で時計回りに移動する．

2 番目の変更が終了した時点での参加者におけるマラソン大会中の衝突は 0 回となる．

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

入力例 3

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

出力例 3

9265409

1 番目の変更が終了した時点での参加者は 3 人である．それぞれの参加者についての情報は以下のようになる．

1. ゼッケン 58\,683 を着用し，地点 58\,683 からスタートする．1 ビョウあたり 28\,489 の速度で時計回りに移動する．
2. ゼッケン 3\,478 を着用し，地点 3\,478 からスタートする．1 ビョウあたり 48\,682\,814 の速度で時計回りに移動する．
3. ゼッケン 28\,482 を着用し，地点 28\,482 からスタートする．1 ビョウあたり 39\,599\,461 の速度で時計回りに移動する．

1 番目の変更が終了した時点での参加者におけるマラソン大会中の衝突は 967\,009\,272\,178 回となる．よってマラソン大会中に起こる衝突の回数を 1\,000\,000\,007 で割ったあまりは 9\,265\,409 となる．

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

入力例 4

7 100 100
34 12 46 23 57 63 99
12 34 23 12 34 12 23
5
67 34
99 23
33 34
99 12
23 12

出力例 4

330
264
341
440
341

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