配点: 100 点
問題文
Bitaro 住在一个巨大的圆形湖周围。湖的周长是 L ,Bitaro的房子就在湖边的某个点。从Bitaro家顺时针绕湖一周 x (0 \leqq x < L) 点对点移动 它被称为 x 。目前计划在湖边举办马拉松比赛。
Bitaro听说马拉松赛事的举办时间如下。 编号高达
- 0 它们的编号最大为 L - 1 的号码布 提供了 1 表。马拉松比赛的参赛者将佩戴其中一个号码布。围兜 佩戴 l (0 \leqq l \leqq L - 1的参与者的起点是 l 变为。
- 马拉松比赛开始后,T 参与者以自己的速度绕湖顺时针移动。马拉松比赛开始后,t 拜奥(0 \leqq t \leqq T) 它被称为 t 。
Bitaro 有一份马拉松参赛者名单。目前 N 参与者列在参与者列表中,i 第一个参与者(1 \leqq i \leqq N) 是围兜 磨损 A_i ,1 拜尤·佩里 我们计划以 S_i 的速度绕湖顺时针移动。
根据参赛者名单,Bitaro 出现在马拉松比赛期间。 计算衝突的数量。这里,碰撞的参与者不同 2 它指的是人们在同一位置。严格来说, 满足0 \leqq p < q \leqq L - 1 的整数 满足 p, q 和 0 \leqq t \leqq T 该组由実数 t 组成 (p, q, t) 用于查找满足以下条件的项目数。
- 围兜 一些参与者穿着 p 。 参与者穿着
- 围兜 一些参与者穿着 q 。 参与者穿着
- 围兜 一些参与者穿着 p 和围兜 参与者穿着 q 我和 t 处于同一点。
然而,此后,参加者名单 Q 已进行更改。j 番目 (1 \leqq j \leqq Q)变化是 表示为 2 整数 给出了 X_j, Y_j ,如下所示。
- 目前,围兜 如果参与者列表中列出了以 X_j ,1 拜尤·佩里 我们计划以 Y_j 速度绕湖顺时针移动的人,则将该人从参与者列表中删除。如果没有的话,围兜 将一个新人添加到参与者列表中,该人以 X_j ,1 拜尤·佩里 我们计划以 Y_j 的速度绕湖顺时针移动。
但是,即使完成任何更改后,参与者列表中列出的参与者仍将被删除。 2 保证人数不只1人,且参赛者佩戴的号码布不同。
Bitaro 想知道每次更改完成后,参与者在马拉松比赛中发生的碰撞次数。由于问题陈述的限制,可以证明马拉松赛事中发生的碰撞次数是有限的。
给定有关马拉松赛事和参与者列表更改的信息,计算每次更改结束时参与者在马拉松赛事期间发生的碰撞次数。 1\,000\,000\,007 后的余数。
制約
- 2 \leqq N.
- N \leqq L \leqq 10^9.
- 1 \leqq T \leqq 10^9.
- 0 \leqq A_i \leqq L - 1 (1 \leqq i \leqq N).
- A_i \neq A_j (1 \leqq i < j \leqq N).
- 1 \leqq S_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq Q.
- N + Q \leqq 100\,000.
- 0 \leqq X_j \leqq L - 1 (1 \leqq j \leqq Q).
- 1 \leqq Y_j \leqq 10^9 (1 \leqq j \leqq Q).
- 在任何更改结束时,参与者 人数超过 2 人。
- 在任何改变结束时,参与者都会有不同的起点。 在
- 所有输入值都是整数。
小課題
- (10 点) T = 1,S_i \leqq 2 (1 \leqq i \leqq N),Y_j \leqq 2 (1 \leqq j \leqq Q).
- (8 点) N \leqq 2\,000,Q = 1.
- (11 点) N \leqq 2\,000,Q \leqq 2\,000.
- (27 点) Q = 1.
- (34 点) N + Q \leqq 78\,000.
- (10 点)没有额外的限制。
入力
输入按以下格式给出。 输出
N L T A_1 A_2 \cdots A_N S_1 S_2 \cdots S_N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
出力
Q 行输出。j 行目 (1 \leqq j \leqq Q)是 计算第 j 次变更结束时参与者在马拉松比赛中发生的碰撞次数。 打印除以 1\,000\,000\,007 后的余数。 在第
入力例 1
3 7 2 1 6 3 4 1 6 1 4 2
出力例 1
7
1 次变更结束时,参与者 4 这是一个人。每位参与者的信息如下。 磨损
- 围兜 一些参与者穿着 1 ,点 从 1 开始。 以1 拜尤·佩里 我们计划以 4 的速度顺时针移动。 在第
- 围兜 一些参与者穿着 6 ,点 从 6 开始。 以1 拜尤·佩里 我们计划以 1 的速度顺时针移动。 在第
- 围兜 一些参与者穿着 3 ,点 从 3 开始。 以1 拜尤·佩里 我们计划以 6 的速度顺时针移动。 在第
- 围兜 一些参与者穿着 4 ,点 从 4 开始。 以1 拜尤·佩里 我们计划以 2 的速度顺时针移动。 在第
1 次变更结束时,参赛者在马拉松比赛中发生的碰撞情况如下: 7 次。
- 時刻 \frac{1}{4} ,围兜 参与者在同一地点佩戴 3 和围兜 参与者穿着 4 我在 \frac{9}{2} 。 在第
- 時刻 \frac{3}{5} ,围兜 参与者在同一地点佩戴 3 和围兜 参与者穿着 6 我在 \frac{33}{5} 。 在第
- 時刻 \frac{3}{2} ,围兜 参与者在同一地点佩戴 1 和围兜 参与者穿着 4 我在 0 。 在第
- 時刻 \frac{5}{3} ,围兜 参与者在同一地点佩戴 1 和围兜 参与者穿着 6 我在 \frac{2}{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
出力例 2
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
出力例 3
9265409
1 次变更结束时,参与者 3 这是一个人。每位参与者的信息如下。 磨损
- 围兜 一些参与者穿着 58\,683 ,点 从 58\,683 开始。 以1 拜尤·佩里 我们计划以 28\,489 的速度顺时针移动。 在第
- 围兜 一些参与者穿着 3\,478 ,点 从 3\,478 开始。 以1 拜尤·佩里 我们计划以 48\,682\,814 的速度顺时针移动。 在第
- 围兜 一些参与者穿着 28\,482 ,点 从 28\,482 开始。 以1 拜尤·佩里 我们计划以 39\,599\,461 的速度顺时针移动。 在第
1 次变更结束时,参赛者在马拉松比赛中发生的碰撞次数为 967\,009\,272\,178 次。因此,马拉松比赛中发生的碰撞次数为 除以 1\,000\,000\,007 后的余数为 9\,265\,409 变为。
此输入示例是一个小作业。 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
出力例 4
330 264 341 440 341
此输入示例是一个小作业。 3,5,6 满足约束。