题目描述

小 F 住在围绕一个大圆形湖泊的周围。湖泊的周长是 $l$，湖泊周围的某个地点是小 F 的家。从小 F 的家开始沿湖泊周围顺时针移动 $x$ （$0 \le x < l$） 的地点被称为地点 $x$。

现在，小 F 计划在湖泊周围举行马拉松比赛。比赛规则如下：

• 准备了编号从 $0$ 到 $l-1$ 的号码布各一张。每位参赛者佩戴其中一张号码布。
• 佩戴号码布 $x$（$0 \le x \le l-1$）的参赛者起点为地点 $x$。
• 比赛开始后，参赛者在 $t$ 秒内以各自速度沿湖顺时针移动。若在某时刻 $t'$（实数，$0 \le t' \le t$）两名不同参赛者位于同一地点，则称为一次冲突。

初始有 $n$ 位参赛者：第 $i$ 位参赛者佩戴号码布 $a_i$ 且速度为 $s_i$（单位：地点/秒）。随后进行了 $q$ 次名单修改。第 $j$ 次修改由一对整数 $(x_j, y_j)$ 表示：

• 若当前名单中存在一位佩戴号码布 $x_j$ 且速度为 $y_j$ 的参赛者，则将其从名单中删除；
• 否则，向名单中添加这样一位参赛者。

保证每次修改结束后名单中至少有 $2$ 人，并且所有参赛者的号码布互不相同。

请在每次修改结束后，输出当前名单在比赛期间发生的冲突次数对 $10^9+7$ 取模的结果。

输入格式

第一行：三个整数 $n, l, t$。

第二行：$n$ 个整数 $a_i$。

第三行：$n$ 个整数 $s_i$。

第四行：一个整数 $q$。

接下来 $q$ 行，每行包含一对整数 $(x_j, y_j)$，表示第 $j$ 次名单修改。

输出格式

输出 $q$ 行，第 $j$ 行（$1 \le j \le q$）为第 $j$ 次修改结束后当前参赛者的冲突次数对 $10^9+7$ 取模的结果。

样例 #1

输入

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

输出

7

样例 #2

输入

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

输出

1
0

样例 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 \le n$，$1 \le q$，$n + q \le 100,000$；
• $n \le l \le 10^9$；
• $1 \le t,y_j,s_i \le 10^9$；
• $0 \le x_j \le l-1$；
• $0 \le a_i \le l-1$ 且对任意 $i\ne j$ 有 $a_i \ne a_j$。

特殊性质 A：保证 $t = 1$，$s_i \le 2$ ，$y_j \le 2$。