Условие задачи

Битаро живёт на берегу большого круглого озера. Длина окружности озера равна $L$, и в некоторой точке на берегу озера находится дом Битаро. Точку, в которую можно попасть, пройдя от дома Битаро по берегу озера по часовой стрелке расстояние $x$ ($0 \le x < L$), назовём точкой $x$. В настоящее время планируется марафонский забег вокруг озера.

Битаро услышал, что марафон планируется провести следующим образом:

• Подготовлены нагрудные номера от $0$ до $L - 1$, по $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$ за $1$ секунду.

На основе списка участников Битаро нашёл количество столкновений, которые произойдут во время марафона. Здесь под столкновением понимается нахождение $2$ различных участников в одной и той же точке. Строго говоря, он нашёл количество троек $(p, q, t)$, состоящих из целых чисел $p, q$, удовлетворяющих условию $0 \le p < q \le L - 1$, и вещественного числа $t$, удовлетворяющего условию $0 \le t \le T$, для которых выполняются следующие условия:

• Есть участник с номером $p$.
• Есть участник с номером $q$.
• Участник с номером $p$ и участник с номером $q$ в момент $t$ находятся в одной и той же точке.

Однако после этого в список участников было внесено $Q$ изменений. $j$-е изменение ($1 \le j \le Q$) задаётся $2$ целыми числами $X_j, Y_j$ и заключается в следующем:

• Если в текущий момент в списке участников записан человек с номером $X_j$, движущийся вокруг озера по часовой стрелке со скоростью $Y_j$ за $1$ секунду, то этого человека удаляют из списка участников. В противном случае в список участников добавляют нового человека с номером $X_j$, движущегося вокруг озера по часовой стрелке со скоростью $Y_j$ за $1$ секунду.

При этом гарантируется, что после завершения любого изменения в списке участников числится не менее $2$ участников, а номера всех участников попарно различны.

Битаро хочет для состава участников после каждого изменения узнать количество столкновений, происходящих во время марафона. Из ограничений задачи можно доказать, что количество столкновений во время марафона конечно.

По данным о марафоне и об изменениях в списке участников напишите программу, которая для состава участников после каждого изменения найдёт остаток от деления количества столкновений во время марафона на $1000000007$.

Ограничения

• $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$).
• После завершения любого изменения имеется не менее $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 2000$, $Q = 1$.
3. ($11$ баллов) $N \le 2000$, $Q \le 2000$.
4. ($27$ баллов) $Q = 1$.
5. ($34$ баллов) $N + Q \le 78000$.
6. ($10$ баллов) Дополнительных ограничений нет.

Входные данные

Входные данные даны в следующем формате: $$\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}$$

Выходные данные

Выведите $Q$ строк. В $j$-й строке ($1 \le j \le Q$) выведите остаток от деления на $1000000007$ количества столкновений, происходящих во время марафона среди участников после завершения $j$-го изменения.

Пример

Пример 1

Входные данные

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

Выходные данные

7

Пояснение

После завершения $1$-го изменения участников $4$. Информация о каждом участнике следующая:

1. Носит номер $1$ и стартует из точки $1$. Движется по часовой стрелке со скоростью $4$ за $1$ секунду.
2. Носит номер $6$ и стартует из точки $6$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
3. Носит номер $3$ и стартует из точки $3$. Движется по часовой стрелке со скоростью $6$ за $1$ секунду.
4. Носит номер $4$ и стартует из точки $4$. Движется по часовой стрелке со скоростью $2$ за $1$ секунду.

Среди участников после завершения $1$-го изменения во время марафона происходят следующие $7$ столкновений:

1. В момент $1 \div 4$ участник с номером $3$ и участник с номером $4$ находятся в одной и той же точке $9 \div 2$.
2. В момент $3 \div 5$ участник с номером $3$ и участник с номером $6$ находятся в одной и той же точке $33 \div 5$.
3. В момент $3 \div 2$ участник с номером $1$ и участник с номером $4$ находятся в одной и той же точке $0$.
4. В момент $5 \div 3$ участник с номером $1$ и участник с номером $6$ находятся в одной и той же точке $2 \div 3$.
5. В момент $2$ участник с номером $3$ и участник с номером $4$ находятся в одной и той же точке $1$.
6. В момент $2$ участник с номером $3$ и участник с номером $6$ находятся в одной и той же точке $1$.
7. В момент $2$ участник с номером $4$ и участник с номером $6$ находятся в одной и той же точке $1$.

Этот пример удовлетворяет ограничениям подзадач $2, 3, 4, 5, 6$.

Пример 2

Входные данные

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

Выходные данные

1
0

Пояснение

После завершения $1$-го изменения участников $4$. Информация о каждом участнике следующая:

1. Носит номер $1$ и стартует из точки $1$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
2. Носит номер $3$ и стартует из точки $3$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
3. Носит номер $4$ и стартует из точки $4$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
4. Носит номер $0$ и стартует из точки $0$. Движется по часовой стрелке со скоростью $2$ за $1$ секунду.

Среди участников после завершения $1$-го изменения во время марафона происходит следующее $1$ столкновение:

1. В момент $1$ участник с номером $0$ и участник с номером $1$ находятся в одной и той же точке $2$.

После завершения $2$-го изменения участников $3$. Информация о каждом участнике следующая:

1. Носит номер $3$ и стартует из точки $3$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
2. Носит номер $4$ и стартует из точки $4$. Движется по часовой стрелке со скоростью $1$ за $1$ секунду.
3. Носит номер $0$ и стартует из точки $0$. Движется по часовой стрелке со скоростью $2$ за $1$ секунду.

Среди участников после завершения $2$-го изменения во время марафона происходит $0$ столкновений.

Этот пример удовлетворяет ограничениям подзадач $1, 3, 5, 6$.

Пример 3

Входные данные

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Выходные данные

9265409

Пояснение

После завершения $1$-го изменения участников $3$. Информация о каждом участнике следующая:

1. Носит номер $58683$ и стартует из точки $58683$. Движется по часовой стрелке со скоростью $28489$ за $1$ секунду.
2. Носит номер $3478$ и стартует из точки $3478$. Движется по часовой стрелке со скоростью $48682814$ за $1$ секунду.
3. Носит номер $28482$ и стартует из точки $28482$. Движется по часовой стрелке со скоростью $39599461$ за $1$ секунду.

Среди участников после завершения $1$-го изменения во время марафона происходит $967009272178$ столкновений. Следовательно, остаток от деления количества столкновений во время марафона на $1000000007$ равен $9265409$.

Этот пример удовлетворяет ограничениям подзадач $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

Выходные данные

330
264
341
440
341

Пояснение

Этот пример удовлетворяет ограничениям подзадач $3, 5, 6$.