第 4 题冲突 (`collision`)

CSP-S 复赛模拟赛 25 · 时间限制 1.0 s · 空间限制 256 MB · 63 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 collision.in，输出文件 collision.out。

题目描述

比太郎住在围绕一个大圆形湖泊的周围。湖泊的周长是 $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 的余数。

输入格式

输入按照如下格式给出：

N\ L\ T \qquad A_1\ A_2\ \ldots\ A_N\ S_1\ S_2\ \ldots\ S_N \qquad Q\ X_1\ Y_1 \quad X_2\ Y_2\ ; \quad X_Q\ Y_Q

输出格式

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

样例

样例 1

输入：

输出：

样例 2

输入：

输出：

1
0

样例 3

输入：

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

输出：

样例 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

输出：

提示

样例 1 解释

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

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

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

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

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

样例 2 解释

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

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

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

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

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

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

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

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

样例 3 解释

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

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

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