P12460 [JOI2025 预选赛 R2] 冲突

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

无

无

### 样例 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 分) 没有额外的限制。