Умова задачі

Бітаро живе на березі великого круглого озера. Довжина кола озера дорівнює $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$.