題目描述
Bitaro 住喺一個大圓形湖泊周圍。湖泊一圈嘅長度係 $L$，湖泊周圍嘅某個位置上面有 Bitaro 屋企。由 Bitaro 屋企出發沿住湖泊周圍順時針行 $x$（$0 \le x < L$）去到嘅位置叫做地點 $x$。而家，正喺度策劃緊一場圍住個湖舉行嘅馬拉松大會。
Bitaro 聽講馬拉松大會預計會按以下方式舉行：
- 準備咗編號由 $0$ 到 $L - 1$ 嘅號碼布各 $1$ 張。馬拉松大會嘅參賽者每人會戴其中一張號碼布。戴號碼布 $l$（$0 \le l \le L - 1$）嘅參賽者嘅起點係地點 $l$。
- 馬拉松大會開始之後，喺 $T$ 秒之內，參賽者會以各自嘅速度沿住湖泊周圍順時針移動。由馬拉松大會開始過咗 $t$ 秒（$0 \le t \le T$）嘅時間點叫做時刻 $t$。
Bitaro 拎住馬拉松大會嘅參賽者名單。而家參賽者名單上面寫住 $N$ 個參賽者，第 $i$ 個參賽者（$1 \le i \le N$）戴住號碼布 $A_i$，預計會以每 $1$ 秒 $S_i$ 嘅速度沿住湖泊周圍順時針移動。
根據份參賽者名單，Bitaro 計出咗馬拉松大會期間發生嘅碰撞次數。呢度講嘅碰撞係指 $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$ 人或以上，而且參賽者戴住嘅號碼布全部都唔同。
Bitaro 想知道對於每次修改結束嗰陣嘅參賽者，喺馬拉松大會期間發生嘅碰撞次數。由題目嘅數據範圍可以證明，馬拉松大會期間發生嘅碰撞次數係有限嘅。
俾定馬拉松大會同埋對參賽者名單進行修改嘅資訊，請寫一個程式，求對於每次修改結束嗰陣嘅參賽者，馬拉松大會期間發生嘅碰撞次數除以 $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$ 人或以上。
- 喺任何一次修改結束嗰陣，參賽者嘅起點全部都唔同。
- 輸入嘅數值全部都係整數。
子任務
- （$10$ 分）$T = 1$，$S_i \le 2$（$1 \le i \le N$），$Y_j \le 2$（$1 \le j \le Q$）。
- （$8$ 分）$N \le 2000$，$Q = 1$。
- （$11$ 分）$N \le 2000$，$Q \le 2000$。
- （$27$ 分）$Q = 1$。
- （$34$ 分）$N + Q \le 78000$。
- （$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$ 秒 $4$ 嘅速度順時針移動。
- 戴號碼布 $6$，由地點 $6$ 出發。以每 $1$ 秒 $1$ 嘅速度順時針移動。
- 戴號碼布 $3$，由地點 $3$ 出發。以每 $1$ 秒 $6$ 嘅速度順時針移動。
- 戴號碼布 $4$，由地點 $4$ 出發。以每 $1$ 秒 $2$ 嘅速度順時針移動。
喺第 $1$ 次修改結束嗰陣嘅參賽者入面，馬拉松大會期間發生嘅碰撞有以下 $7$ 次：
- 喺時刻 $1 \div 4$，戴號碼布 $3$ 嘅參賽者同戴號碼布 $4$ 嘅參賽者喺同一個地點 $9 \div 2$。
- 喺時刻 $3 \div 5$，戴號碼布 $3$ 嘅參賽者同戴號碼布 $6$ 嘅參賽者喺同一個地點 $33 \div 5$。
- 喺時刻 $3 \div 2$，戴號碼布 $1$ 嘅參賽者同戴號碼布 $4$ 嘅參賽者喺同一個地點 $0$。
- 喺時刻 $5 \div 3$，戴號碼布 $1$ 嘅參賽者同戴號碼布 $6$ 嘅參賽者喺同一個地點 $2 \div 3$。
- 喺時刻 $2$，戴號碼布 $3$ 嘅參賽者同戴號碼布 $4$ 嘅參賽者喺同一個地點 $1$。
- 喺時刻 $2$，戴號碼布 $3$ 嘅參賽者同戴號碼布 $6$ 嘅參賽者喺同一個地點 $1$。
- 喺時刻 $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$ 嘅速度順時針移動。
- 戴號碼布 $3$，由地點 $3$ 出發。以每 $1$ 秒 $1$ 嘅速度順時針移動。
- 戴號碼布 $4$，由地點 $4$ 出發。以每 $1$ 秒 $1$ 嘅速度順時針移動。
- 戴號碼布 $0$，由地點 $0$ 出發。以每 $1$ 秒 $2$ 嘅速度順時針移動。
喺第 $1$ 次修改結束嗰陣嘅參賽者入面，馬拉松大會期間發生嘅碰撞有以下 $1$ 次：
- 喺時刻 $1$，戴號碼布 $0$ 嘅參賽者同戴號碼布 $1$ 嘅參賽者喺同一個地點 $2$。
第 $2$ 次修改結束嗰陣嘅參賽者有 $3$ 人。關於各個參賽者嘅資訊如下：
- 戴號碼布 $3$，由地點 $3$ 出發。以每 $1$ 秒 $1$ 嘅速度順時針移動。
- 戴號碼布 $4$，由地點 $4$ 出發。以每 $1$ 秒 $1$ 嘅速度順時針移動。
- 戴號碼布 $0$，由地點 $0$ 出發。以每 $1$ 秒 $2$ 嘅速度順時針移動。
喺第 $2$ 次修改結束嗰陣嘅參賽者入面，馬拉松大會期間發生嘅碰撞係 $0$ 次。
呢個範例輸入滿足子任務 $1, 3, 5, 6$ 嘅限制。
範例 3
輸入
2 100000 993754689 58683 3478 28489 48682814 1 28482 39599461
輸出
9265409
解釋
第 $1$ 次修改結束嗰陣嘅參賽者有 $3$ 人。關於各個參賽者嘅資訊如下：
- 戴號碼布 $58683$，由地點 $58683$ 出發。以每 $1$ 秒 $28489$ 嘅速度順時針移動。
- 戴號碼布 $3478$，由地點 $3478$ 出發。以每 $1$ 秒 $48682814$ 嘅速度順時針移動。
- 戴號碼布 $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$ 嘅限制。