問題文

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

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

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

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

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

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

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

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

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

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

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

制約

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

小課題

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

入力

入力は以下の形式で与えられる． $$\begin{aligned} &N \quad L \quad T \\ &A_1 \quad A_2 \quad \dots \quad A_N \\ &S_1 \quad S_2 \quad \dots \quad S_N \\ &Q \\ &X_1 \quad Y_1 \\ &X_2 \quad Y_2 \\ &\vdots \\ &X_Q \quad Y_Q \end{aligned}$$

出力

$Q$ 行に出力せよ．$j$ 行目 ($1 \le j \le Q$) には $j$ 番目の変更が終了した時点での参加者における，マラソン大会中に起こる衝突の回数を $1000000007$ で割ったあまりを出力せよ．

入出力例

入出力例 1

入力

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

出力

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. 時刻 $1 \div 4$ に，ゼッケン $3$ を着用した参加者とゼッケン $4$ を着用した参加者が同じ地点 $9 \div 2$ にいる．
2. 時刻 $3 \div 5$ に，ゼッケン $3$ を着用した参加者とゼッケン $6$ を着用した参加者が同じ地点 $33 \div 5$ にいる．
3. 時刻 $3 \div 2$ に，ゼッケン $1$ を着用した参加者とゼッケン $4$ を着用した参加者が同じ地点 $0$ にいる．
4. 時刻 $5 \div 3$ に，ゼッケン $1$ を着用した参加者とゼッケン $6$ を着用した参加者が同じ地点 $2 \div 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

出力

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

出力

9265409

説明

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

1. ゼッケン $58683$ を着用し，地点 $58683$ からスタートする．$1$ 秒あたり $28489$ の速度で時計回りに移動する．
2. ゼッケン $3478$ を着用し，地点 $3478$ からスタートする．$1$ 秒あたり $48682814$ の速度で時計回りに移動する．
3. ゼッケン $28482$ を着用し，地点 $28482$ からスタートする．$1$ 秒あたり $39599461$ の速度で時計回りに移動する．

$1$ 番目の変更が終了した時点での参加者におけるマラソン大会中の衝突は $967009272178$ 回となる．よってマラソン大会中に起こる衝突の回数を $1000000007$ で割ったあまりは $9265409$ となる．

この入力例は小課題 $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

出力

330
264
341
440
341

説明

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