題目描述
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$ 的限制。