Descripción del problema

Bitaro vive alrededor de un gran lago circular. La circunferencia del lago es $L$, y en cierto punto alrededor del lago se encuentra la casa de Bitaro. El punto al que se llega tras desplazarse una distancia $x$ ($0 \le x < L$) en el sentido de las agujas del reloj alrededor del lago desde la casa de Bitaro se denomina punto $x$. Actualmente se está planeando un maratón que se celebrará alrededor del lago.

Bitaro se enteró de que está previsto que el maratón se lleve a cabo de la siguiente manera:

• Se preparan dorsales numerados del $0$ al $L - 1$, $1$ de cada uno. Cada participante del maratón lleva puesto uno de los dorsales. El punto de salida del participante que lleva el dorsal $l$ ($0 \le l \le L - 1$) es el punto $l$.
• Después de que comience el maratón, durante $T$ segundos, los participantes se desplazan alrededor del lago en el sentido de las agujas del reloj a sus respectivas velocidades. El instante en que han transcurrido $t$ segundos ($0 \le t \le T$) desde el inicio del maratón se denomina instante $t$.

Bitaro tiene la lista de participantes del maratón. Actualmente hay $N$ participantes inscritos en la lista de participantes, y está previsto que el $i$-ésimo participante ($1 \le i \le N$) lleve el dorsal $A_i$ y se desplace alrededor del lago en el sentido de las agujas del reloj a una velocidad de $S_i$ por cada $1$ segundo.

Basándose en la lista de participantes, Bitaro calculó el número de colisiones que ocurren durante el maratón. Aquí, una colisión se refiere a que $2$ participantes distintos se encuentren en el mismo punto. Estrictamente hablando, halló el número de ternas $(p, q, t)$ formadas por enteros $p, q$ que cumplen $0 \le p < q \le L - 1$ y un número real $t$ que cumple $0 \le t \le T$ tales que satisfacen las siguientes condiciones:

• Hay un participante que lleva el dorsal $p$.
• Hay un participante que lleva el dorsal $q$.
• El participante que lleva el dorsal $p$ y el participante que lleva el dorsal $q$ están en el mismo punto en el instante $t$.

Sin embargo, después de eso se realizaron $Q$ modificaciones en la lista de participantes. La $j$-ésima modificación ($1 \le j \le Q$) se representa mediante $2$ enteros $X_j, Y_j$, y es como sigue:

• Actualmente, si en la lista de participantes figura una persona que lleva el dorsal $X_j$ y se desplaza alrededor del lago en el sentido de las agujas del reloj a una velocidad de $Y_j$ por cada $1$ segundo, se elimina a esa persona de la lista de participantes. En caso contrario, se añade a la lista de participantes una nueva persona que lleva el dorsal $X_j$ y se desplaza alrededor del lago en el sentido de las agujas del reloj a una velocidad de $Y_j$ por cada $1$ segundo.

No obstante, se garantiza que al finalizar cualquier modificación hay al menos $2$ participantes inscritos en la lista de participantes, y que los dorsales que llevan los participantes son todos distintos entre sí.

Bitaro quiere saber, para los participantes en el momento en que finaliza cada modificación, el número de colisiones que ocurren durante el maratón. A partir de las restricciones del enunciado, se puede demostrar que el número de colisiones que ocurren durante el maratón es finito.

Dada la información sobre el maratón y las modificaciones en la lista de participantes, escribe un programa para hallar, para los participantes en el momento en que finaliza cada modificación, el resto de dividir el número de colisiones que ocurren durante el maratón entre $1000000007$.

Restricciones

• $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$).
• Al finalizar cualquier modificación, hay al menos $2$ participantes.
• Al finalizar cualquier modificación, los puntos de salida de los participantes son todos distintos entre sí.
• Todos los valores de entrada son enteros.

Subtareas

1. ($10$ puntos) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ puntos) $N \le 2000$, $Q = 1$.
3. ($11$ puntos) $N \le 2000$, $Q \le 2000$.
4. ($27$ puntos) $Q = 1$.
5. ($34$ puntos) $N + Q \le 78000$.
6. ($10$ puntos) Sin restricciones adicionales.

Entrada

La entrada se proporciona en el siguiente formato: $$\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}$$

Salida

Imprime $Q$ líneas. En la $j$-ésima línea ($1 \le j \le Q$), imprime el resto de dividir entre $1000000007$ el número de colisiones que ocurren durante el maratón entre los participantes en el momento en que finaliza la $j$-ésima modificación.

Ejemplo

Ejemplo 1

Entrada

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

Salida

7

Explicación

Hay $4$ participantes en el momento en que finaliza la $1$-ra modificación. La información sobre cada participante es la siguiente:

1. Lleva el dorsal $1$ y sale del punto $1$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $4$ por cada $1$ segundo.
2. Lleva el dorsal $6$ y sale del punto $6$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
3. Lleva el dorsal $3$ y sale del punto $3$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $6$ por cada $1$ segundo.
4. Lleva el dorsal $4$ y sale del punto $4$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $2$ por cada $1$ segundo.

Entre los participantes en el momento en que finaliza la $1$-ra modificación, ocurren las siguientes $7$ colisiones durante el maratón:

1. En el instante $1 \div 4$, el participante con el dorsal $3$ y el participante con el dorsal $4$ están en el mismo punto $9 \div 2$.
2. En el instante $3 \div 5$, el participante con el dorsal $3$ y el participante con el dorsal $6$ están en el mismo punto $33 \div 5$.
3. En el instante $3 \div 2$, el participante con el dorsal $1$ y el participante con el dorsal $4$ están en el mismo punto $0$.
4. En el instante $5 \div 3$, el participante con el dorsal $1$ y el participante con el dorsal $6$ están en el mismo punto $2 \div 3$.
5. En el instante $2$, el participante con el dorsal $3$ y el participante con el dorsal $4$ están en el mismo punto $1$.
6. En el instante $2$, el participante con el dorsal $3$ y el participante con el dorsal $6$ están en el mismo punto $1$.
7. En el instante $2$, el participante con el dorsal $4$ y el participante con el dorsal $6$ están en el mismo punto $1$.

Este ejemplo de entrada cumple las restricciones de las Subtareas $2, 3, 4, 5, 6$.

Ejemplo 2

Entrada

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

Salida

1
0

Explicación

Hay $4$ participantes en el momento en que finaliza la $1$-ra modificación. La información sobre cada participante es la siguiente:

1. Lleva el dorsal $1$ y sale del punto $1$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
2. Lleva el dorsal $3$ y sale del punto $3$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
3. Lleva el dorsal $4$ y sale del punto $4$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
4. Lleva el dorsal $0$ y sale del punto $0$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $2$ por cada $1$ segundo.

Entre los participantes en el momento en que finaliza la $1$-ra modificación, ocurre la siguiente $1$ colisión durante el maratón:

1. En el instante $1$, el participante con el dorsal $0$ y el participante con el dorsal $1$ están en el mismo punto $2$.

Hay $3$ participantes en el momento en que finaliza la $2$-da modificación. La información sobre cada participante es la siguiente:

1. Lleva el dorsal $3$ y sale del punto $3$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
2. Lleva el dorsal $4$ y sale del punto $4$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $1$ por cada $1$ segundo.
3. Lleva el dorsal $0$ y sale del punto $0$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $2$ por cada $1$ segundo.

Entre los participantes en el momento en que finaliza la $2$-da modificación, ocurren $0$ colisiones durante el maratón.

Este ejemplo de entrada cumple las restricciones de las Subtareas $1, 3, 5, 6$.

Ejemplo 3

Entrada

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Salida

9265409

Explicación

Hay $3$ participantes en el momento en que finaliza la $1$-ra modificación. La información sobre cada participante es la siguiente:

1. Lleva el dorsal $58683$ y sale del punto $58683$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $28489$ por cada $1$ segundo.
2. Lleva el dorsal $3478$ y sale del punto $3478$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $48682814$ por cada $1$ segundo.
3. Lleva el dorsal $28482$ y sale del punto $28482$. Se desplaza en el sentido de las agujas del reloj a una velocidad de $39599461$ por cada $1$ segundo.

Entre los participantes en el momento en que finaliza la $1$-ra modificación, ocurren $967009272178$ colisiones durante el maratón. Por lo tanto, el resto de dividir el número de colisiones que ocurren durante el maratón entre $1000000007$ es $9265409$.

Este ejemplo de entrada cumple las restricciones de las Subtareas $2, 3, 4, 5, 6$.

Ejemplo 4

Entrada

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

Salida

330
264
341
440
341

Explicación

Este ejemplo de entrada cumple las restricciones de las Subtareas $3, 5, 6$.