题目描述

比太郎住在围绕一个大圆形湖泊的周围。湖泊的周长是 $L$，湖泊周围的某个地点是比太郎的家。从比太郎的家开始沿湖泊周围顺时针移动 $x$ ($0 \le x < L$) 的地点被称为地点 $x$。现在，计划在湖泊周围举行马拉松比赛。

比太郎听说马拉松比赛将按以下方式进行：

• 准备了从 $0$ 到 $L-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$，并计划以每秒 $S_i$ 的速度沿湖泊周围顺时针移动。

根据参与者名单，比太郎计算了马拉松比赛中发生的冲突次数。这里，冲突是指两个不同的参与者在同一地点的情况。严格来说，计算满足以下条件的整数三元组 $(p, q, t)$ 的个数，其中 $0 \le p < q \le L-1$，$0 \le t \le T$ 是一个实数：

• 有佩戴号码布 $p$ 的参与者。
• 有佩戴号码布 $q$ 的参与者。
• 在时刻 $t$，佩戴号码布 $p$ 的参与者和佩戴号码布 $q$ 的参与者在同一地点。

然而，之后参与者名单进行了 $Q$ 次更改。第 $j$ 次 ($1 \le j \le Q$) 更改由两个整数 $X_j, Y_j$ 表示，如下所示：

• 如果当前参与者名单中有名佩戴号码布 $X_j$，以每秒 $Y_j$ 的速度沿湖泊周围顺时针移动的人，则将其从名单中删除。否则，将一名佩戴号码布 $X_j$，以每秒 $Y_j$ 的速度沿湖泊周围顺时针移动的人添加到参与者名单中。

请注意，在任何更改结束后，参与者名单中至少有 2 人，并且参与者佩戴的号码布都不同。

比太郎想知道每次更改结束后，当前参与者在马拉松比赛中发生的冲突次数。根据问题描述的约束，可以证明马拉松比赛中发生的冲突次数是有限的。

给定马拉松比赛和参与者名单更改的信息，请编写一个程序，计算每次更改结束后，当前参与者在马拉松比赛中发生的冲突次数除以 $1\,000\,000\,007$ 的余数。

输入格式

输入按照如下格式给出：

$$\begin{aligned} &N\ L\ T\\ &A_1\ A_2\ \ldots\ A_N\\ &S_1\ S_2\ \ldots\ S_N\\ &Q\\ &X_1\ Y_1\\ &X_2\ Y_2\\ &\vdots\\ &X_Q\ Y_Q\\ \end{aligned}$$

输出格式

输出 $Q$ 行。第 $j$ 行 ($1 \le j \le Q$) 输出第 $j$ 次更改结束后，当前参与者在马拉松比赛中发生的冲突次数除以 $1\,000\,000\,007$ 的余数。

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

7

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

1
0

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

9265409

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

提示

样例 1 解释

第一次更改结束后，有 4 位参与者。每个参与者的信息如下：

1. 佩戴号码布 1，从地点 1 出发。以每秒 4 的速度顺时针移动。
2. 佩戴号码布 6，从地点 6 出发。以每秒 1 的速度顺时针移动。
3. 佩戴号码布 3，从地点 3 出发。以每秒 6 的速度顺时针移动。
4. 佩戴号码布 4，从地点 4 出发。以每秒 2 的速度顺时针移动。

第一次更改结束后，马拉松比赛中发生以下 7 次冲突：

1. 在时刻 $1/4$，佩戴号码布 3 的参与者和佩戴号码布 4 的参与者在同一地点 $9/2$。
2. 在时刻 $3/5$，佩戴号码布 3 的参与者和佩戴号码布 6 的参与者在同一地点 $33/5$。
3. 在时刻 $3/2$，佩戴号码布 1 的参与者和佩戴号码布 4 的参与者在同一地点 $0$。
4. 在时刻 $5/3$，佩戴号码布 1 的参与者和佩戴号码布 6 的参与者在同一地点 $2/3$。
5. 在时刻 $2$，佩戴号码布 3 的参与者和佩戴号码布 4 的参与者在同一地点 $1$。
6. 在时刻 $2$，佩戴号码布 3 的参与者和佩戴号码布 6 的参与者在同一地点 $1$。
7. 在时刻 $2$，佩戴号码布 4 的参与者和佩戴号码布 6 的参与者在同一地点 $1$。

这个输入样例满足子任务 2, 3, 4, 5, 6 的约束。

样例 2 解释

第一次更改结束后，有 4 位参与者。每个参与者的信息如下：

1. 佩戴号码布 1，从地点 1 出发。以每秒 1 的速度顺时针移动。
2. 佩戴号码布 3，从地点 3 出发。以每秒 1 的速度顺时针移动。
3. 佩戴号码布 4，从地点 4 出发。以每秒 1 的速度顺时针移动。
4. 佩戴号码布 0，从地点 0 出发。以每秒 2 的速度顺时针移动。

第一次更改结束后，马拉松比赛中发生以下 1 次冲突：

1. 在时刻 $1$，佩戴号码布 0 的参与者和佩戴号码布 1 的参与者在同一地点 $2$。

第二次更改结束后，有 3 位参与者。每个参与者的信息如下：

1. 佩戴号码布 3，从地点 3 出发。以每秒 1 的速度顺时针移动。
2. 佩戴号码布 4，从地点 4 出发。以每秒 1 的速度顺时针移动。
3. 佩戴号码布 0，从地点 0 出发。以每秒 2 的速度顺时针移动。

第二次更改结束后，马拉松比赛中发生的冲突次数为 0。

这个输入样例满足子任务 1, 3, 5, 6 的约束。

样例 3 解释

第一次更改结束后，有 3 位参与者。每个参与者的信息如下：

1. 佩戴号码布 58683，从地点 58683 出发。以每秒 28489 的速度顺时针移动。
2. 佩戴号码布 3478，从地点 3478 出发。以每秒 48682814 的速度顺时针移动。
3. 佩戴号码布 28482，从地点 28482 出发。以每秒 39599461 的速度顺时针移动。

第一次更改结束后，马拉松比赛中发生的冲突次数为 967009272178 次。因此，马拉松比赛中发生的冲突次数除以 $1\,000\,000\,007$ 的余数为 $9265409$。

这个输入样例满足子任务 2, 3, 4, 5, 6 的约束。

数据范围

• $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 \neq 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 100\,000$
• $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 2\,000$, $Q = 1$.
3. (11 分) $N \le 2\,000$, $Q \le 2\,000$.
4. (27 分) $Q = 1$.
5. (34 分) $N + Q \le 78\,000$.
6. (10 分) 没有额外的限制。