Problem Statement

Bitaro lives around a large circular lake. The circumference of the lake is $L$, and Bitaro's house is located at a certain point on the circumference of the lake. The point reached by moving a distance of $x$ ($0 \le x < L$) clockwise along the circumference of the lake from Bitaro's house is called point $x$. Currently, a marathon race to be held around the lake is being planned.

Bitaro heard that the marathon race is scheduled to be held as follows:

• Bibs numbered from $0$ to $L - 1$ are prepared, $1$ of each. Each participant in the marathon race wears one of the bibs. The starting point of the participant wearing bib $l$ ($0 \le l \le L - 1$) is point $l$.
• After the marathon race starts, for $T$ seconds, the participants move clockwise around the lake at their respective speeds. The moment when $t$ seconds ($0 \le t \le T$) have elapsed since the start of the marathon race is called time $t$.

Bitaro has the participant roster for the marathon race. Currently, $N$ participants are listed on the participant roster, and the $i$-th participant ($1 \le i \le N$) is scheduled to wear bib $A_i$ and move clockwise around the lake at a speed of $S_i$ per $1$ second.

Based on the participant roster, Bitaro found the number of collisions that occur during the marathon race. Here, a collision refers to $2$ different participants being at the same point. Strictly speaking, he found the number of triples $(p, q, t)$ consisting of integers $p, q$ satisfying $0 \le p < q \le L - 1$ and a real number $t$ satisfying $0 \le t \le T$ that satisfy the following conditions:

• There is a participant wearing bib $p$.
• There is a participant wearing bib $q$.
• The participant wearing bib $p$ and the participant wearing bib $q$ are at the same point at time $t$.

However, after that, $Q$ modifications were made to the participant roster. The $j$-th modification ($1 \le j \le Q$) is represented by $2$ integers $X_j, Y_j$, and is as follows:

• Currently, if a person who wears bib $X_j$ and moves clockwise around the lake at a speed of $Y_j$ per $1$ second is listed on the participant roster, remove that person from the participant roster. Otherwise, newly add a person who wears bib $X_j$ and moves clockwise around the lake at a speed of $Y_j$ per $1$ second to the participant roster.

Here, at the moment when any modification finishes, it is guaranteed that there are $2$ or more participants listed on the participant roster, and that the bibs worn by the participants are mutually distinct.

Bitaro wants to know, for the participants at the moment when each modification finishes, the number of collisions that occur during the marathon race. From the constraints of the problem statement, it can be proved that the number of collisions that occur during the marathon race is finite.

Given the information about the marathon race and the modifications to the participant roster, write a program to find, for the participants at the moment when each modification finishes, the remainder when the number of collisions that occur during the marathon race is divided by $1000000007$.

Constraints

• $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 \ne 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 100000$.
• $0 \le X_j \le L - 1$ ($1 \le j \le Q$).
• $1 \le Y_j \le 10^9$ ($1 \le j \le Q$).
• At the moment when any modification finishes, there are $2$ or more participants.
• At the moment when any modification finishes, the starting points of the participants are mutually distinct.
• All input values are integers.

Subtasks

1. ($10$ points) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ points) $N \le 2000$, $Q = 1$.
3. ($11$ points) $N \le 2000$, $Q \le 2000$.
4. ($27$ points) $Q = 1$.
5. ($34$ points) $N + Q \le 78000$.
6. ($10$ points) No additional constraints.

Input

The input is given in the following format: $$\begin{aligned} &N \quad L \quad T \\ &A_1 \quad A_2 \quad \dots \quad A_N \\ &S_1 \quad S_2 \quad \dots \quad S_N \\ &Q \\ &X_1 \quad Y_1 \\ &X_2 \quad Y_2 \\ &\vdots \\ &X_Q \quad Y_Q \end{aligned}$$

Output

Output $Q$ lines. On the $j$-th line ($1 \le j \le Q$), output the remainder when the number of collisions that occur during the marathon race among the participants at the moment when the $j$-th modification finishes is divided by $1000000007$.

Sample

Sample 1

Input

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

Output

7

Explanation

There are $4$ participants at the moment when the $1$-st modification finishes. The information about each participant is as follows:

1. Wears bib $1$ and starts from point $1$. Moves clockwise at a speed of $4$ per $1$ second.
2. Wears bib $6$ and starts from point $6$. Moves clockwise at a speed of $1$ per $1$ second.
3. Wears bib $3$ and starts from point $3$. Moves clockwise at a speed of $6$ per $1$ second.
4. Wears bib $4$ and starts from point $4$. Moves clockwise at a speed of $2$ per $1$ second.

Among the participants at the moment when the $1$-st modification finishes, the following $7$ collisions occur during the marathon race:

1. At time $1 \div 4$, the participant wearing bib $3$ and the participant wearing bib $4$ are at the same point $9 \div 2$.
2. At time $3 \div 5$, the participant wearing bib $3$ and the participant wearing bib $6$ are at the same point $33 \div 5$.
3. At time $3 \div 2$, the participant wearing bib $1$ and the participant wearing bib $4$ are at the same point $0$.
4. At time $5 \div 3$, the participant wearing bib $1$ and the participant wearing bib $6$ are at the same point $2 \div 3$.
5. At time $2$, the participant wearing bib $3$ and the participant wearing bib $4$ are at the same point $1$.
6. At time $2$, the participant wearing bib $3$ and the participant wearing bib $6$ are at the same point $1$.
7. At time $2$, the participant wearing bib $4$ and the participant wearing bib $6$ are at the same point $1$.

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.

Sample 2

Input

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

Output

1
0

Explanation

There are $4$ participants at the moment when the $1$-st modification finishes. The information about each participant is as follows:

1. Wears bib $1$ and starts from point $1$. Moves clockwise at a speed of $1$ per $1$ second.
2. Wears bib $3$ and starts from point $3$. Moves clockwise at a speed of $1$ per $1$ second.
3. Wears bib $4$ and starts from point $4$. Moves clockwise at a speed of $1$ per $1$ second.
4. Wears bib $0$ and starts from point $0$. Moves clockwise at a speed of $2$ per $1$ second.

Among the participants at the moment when the $1$-st modification finishes, the following $1$ collision occurs during the marathon race:

1. At time $1$, the participant wearing bib $0$ and the participant wearing bib $1$ are at the same point $2$.

There are $3$ participants at the moment when the $2$-nd modification finishes. The information about each participant is as follows:

1. Wears bib $3$ and starts from point $3$. Moves clockwise at a speed of $1$ per $1$ second.
2. Wears bib $4$ and starts from point $4$. Moves clockwise at a speed of $1$ per $1$ second.
3. Wears bib $0$ and starts from point $0$. Moves clockwise at a speed of $2$ per $1$ second.

Among the participants at the moment when the $2$-nd modification finishes, $0$ collisions occur during the marathon race.

This sample input satisfies the constraints of Subtasks $1, 3, 5, 6$.

Sample 3

Input

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Output

9265409

Explanation

There are $3$ participants at the moment when the $1$-st modification finishes. The information about each participant is as follows:

1. Wears bib $58683$ and starts from point $58683$. Moves clockwise at a speed of $28489$ per $1$ second.
2. Wears bib $3478$ and starts from point $3478$. Moves clockwise at a speed of $48682814$ per $1$ second.
3. Wears bib $28482$ and starts from point $28482$. Moves clockwise at a speed of $39599461$ per $1$ second.

Among the participants at the moment when the $1$-st modification finishes, $967009272178$ collisions occur during the marathon race. Therefore, the remainder when the number of collisions that occur during the marathon race is divided by $1000000007$ is $9265409$.

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.

Sample 4

Input

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

Output

330
264
341
440
341

Explanation

This sample input satisfies the constraints of Subtasks $3, 5, 6$.