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