Testo del problema

Bitaro vive intorno a un grande lago circolare. La circonferenza del lago è $L$ e in un certo punto lungo la riva del lago si trova la casa di Bitaro. Il punto raggiunto muovendosi di una distanza $x$ ($0 \le x < L$) in senso orario lungo la riva del lago a partire dalla casa di Bitaro è chiamato punto $x$. Attualmente è in fase di progettazione una maratona che si svolgerà intorno al lago.

Bitaro ha sentito dire che la maratona dovrebbe svolgersi come segue:

• Vengono preparati dei pettorali numerati da $0$ a $L - 1$, $1$ per ciascun numero. Ogni partecipante alla maratona indossa uno dei pettorali. Il punto di partenza del partecipante che indossa il pettorale $l$ ($0 \le l \le L - 1$) è il punto $l$.
• Dopo la partenza della maratona, per $T$ secondi, i partecipanti si muovono in senso orario intorno al lago ciascuno alla propria velocità. L'istante in cui sono trascorsi $t$ secondi ($0 \le t \le T$) dalla partenza della maratona è chiamato istante $t$.

Bitaro possiede l'elenco dei partecipanti alla maratona. Attualmente nell'elenco dei partecipanti sono registrati $N$ partecipanti, e l'$i$-esimo partecipante ($1 \le i \le N$) dovrebbe indossare il pettorale $A_i$ e muoversi in senso orario intorno al lago a una velocità di $S_i$ per $1$ secondo.

Sulla base dell'elenco dei partecipanti, Bitaro ha calcolato il numero di collisioni che avvengono durante la maratona. Qui, per collisione si intende il fatto che $2$ partecipanti diversi si trovino nello stesso punto. Più precisamente, ha trovato il numero di terne $(p, q, t)$ formate da interi $p, q$ tali che $0 \le p < q \le L - 1$ e da un numero reale $t$ tale che $0 \le t \le T$ che soddisfano le seguenti condizioni:

• C'è un partecipante che indossa il pettorale $p$.
• C'è un partecipante che indossa il pettorale $q$.
• Il partecipante che indossa il pettorale $p$ e il partecipante che indossa il pettorale $q$ si trovano nello stesso punto all'istante $t$.

Tuttavia, successivamente sono state apportate $Q$ modifiche all'elenco dei partecipanti. La $j$-esima modifica ($1 \le j \le Q$) è rappresentata da $2$ interi $X_j, Y_j$, ed è la seguente:

• Attualmente, se nell'elenco dei partecipanti è registrata una persona che indossa il pettorale $X_j$ e si muove in senso orario intorno al lago a una velocità di $Y_j$ per $1$ secondo, tale persona viene rimossa dall'elenco dei partecipanti. Altrimenti, viene aggiunta all'elenco dei partecipanti una nuova persona che indossa il pettorale $X_j$ e si muove in senso orario intorno al lago a una velocità di $Y_j$ per $1$ secondo.

Si garantisce comunque che, al termine di qualsiasi modifica, nell'elenco dei partecipanti siano registrati almeno $2$ partecipanti e che i pettorali indossati dai partecipanti siano tutti distinti.

Bitaro vuole conoscere, per i partecipanti presenti al termine di ciascuna modifica, il numero di collisioni che avvengono durante la maratona. Dalle assunzioni del testo del problema si può dimostrare che il numero di collisioni che avvengono durante la maratona è finito.

Date le informazioni sulla maratona e sulle modifiche all'elenco dei partecipanti, scrivi un programma per trovare, per i partecipanti presenti al termine di ciascuna modifica, il resto della divisione per $1000000007$ del numero di collisioni che avvengono durante la maratona.

Assunzioni

• $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 termine di qualsiasi modifica ci sono almeno $2$ partecipanti.
• Al termine di qualsiasi modifica i punti di partenza dei partecipanti sono tutti distinti.
• Tutti i valori in input sono interi.

Subtask

1. ($10$ punti) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ punti) $N \le 2000$, $Q = 1$.
3. ($11$ punti) $N \le 2000$, $Q \le 2000$.
4. ($27$ punti) $Q = 1$.
5. ($34$ punti) $N + Q \le 78000$.
6. ($10$ punti) Nessuna limitazione aggiuntiva.

Input

L'input è fornito nel seguente 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}$$

Output

Stampa $Q$ righe. Sulla $j$-esima riga ($1 \le j \le Q$), stampa il resto della divisione per $1000000007$ del numero di collisioni che avvengono durante la maratona tra i partecipanti presenti al termine della $j$-esima modifica.

Esempio

Esempio 1

Input

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

Output

7

Spiegazione

Ci sono $4$ partecipanti al termine della $1$-a modifica. Le informazioni su ciascun partecipante sono le seguenti:

1. Indossa il pettorale $1$ e parte dal punto $1$. Si muove in senso orario a una velocità di $4$ per $1$ secondo.
2. Indossa il pettorale $6$ e parte dal punto $6$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
3. Indossa il pettorale $3$ e parte dal punto $3$. Si muove in senso orario a una velocità di $6$ per $1$ secondo.
4. Indossa il pettorale $4$ e parte dal punto $4$. Si muove in senso orario a una velocità di $2$ per $1$ secondo.

Tra i partecipanti presenti al termine della $1$-a modifica, durante la maratona avvengono le seguenti $7$ collisioni:

1. All'istante $1 \div 4$, il partecipante con il pettorale $3$ e il partecipante con il pettorale $4$ si trovano nello stesso punto $9 \div 2$.
2. All'istante $3 \div 5$, il partecipante con il pettorale $3$ e il partecipante con il pettorale $6$ si trovano nello stesso punto $33 \div 5$.
3. All'istante $3 \div 2$, il partecipante con il pettorale $1$ e il partecipante con il pettorale $4$ si trovano nello stesso punto $0$.
4. All'istante $5 \div 3$, il partecipante con il pettorale $1$ e il partecipante con il pettorale $6$ si trovano nello stesso punto $2 \div 3$.
5. All'istante $2$, il partecipante con il pettorale $3$ e il partecipante con il pettorale $4$ si trovano nello stesso punto $1$.
6. All'istante $2$, il partecipante con il pettorale $3$ e il partecipante con il pettorale $6$ si trovano nello stesso punto $1$.
7. All'istante $2$, il partecipante con il pettorale $4$ e il partecipante con il pettorale $6$ si trovano nello stesso punto $1$.

Questo esempio di input soddisfa le assunzioni dei Subtask $2, 3, 4, 5, 6$.

Esempio 2

Input

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

Output

1
0

Spiegazione

Ci sono $4$ partecipanti al termine della $1$-a modifica. Le informazioni su ciascun partecipante sono le seguenti:

1. Indossa il pettorale $1$ e parte dal punto $1$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
2. Indossa il pettorale $3$ e parte dal punto $3$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
3. Indossa il pettorale $4$ e parte dal punto $4$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
4. Indossa il pettorale $0$ e parte dal punto $0$. Si muove in senso orario a una velocità di $2$ per $1$ secondo.

Tra i partecipanti presenti al termine della $1$-a modifica, durante la maratona avviene la seguente $1$ collisione:

1. All'istante $1$, il partecipante con il pettorale $0$ e il partecipante con il pettorale $1$ si trovano nello stesso punto $2$.

Ci sono $3$ partecipanti al termine della $2$-a modifica. Le informazioni su ciascun partecipante sono le seguenti:

1. Indossa il pettorale $3$ e parte dal punto $3$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
2. Indossa il pettorale $4$ e parte dal punto $4$. Si muove in senso orario a una velocità di $1$ per $1$ secondo.
3. Indossa il pettorale $0$ e parte dal punto $0$. Si muove in senso orario a una velocità di $2$ per $1$ secondo.

Tra i partecipanti presenti al termine della $2$-a modifica, durante la maratona avvengono $0$ collisioni.

Questo esempio di input soddisfa le assunzioni dei Subtask $1, 3, 5, 6$.

Esempio 3

Input

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Output

9265409

Spiegazione

Ci sono $3$ partecipanti al termine della $1$-a modifica. Le informazioni su ciascun partecipante sono le seguenti:

1. Indossa il pettorale $58683$ e parte dal punto $58683$. Si muove in senso orario a una velocità di $28489$ per $1$ secondo.
2. Indossa il pettorale $3478$ e parte dal punto $3478$. Si muove in senso orario a una velocità di $48682814$ per $1$ secondo.
3. Indossa il pettorale $28482$ e parte dal punto $28482$. Si muove in senso orario a una velocità di $39599461$ per $1$ secondo.

Tra i partecipanti presenti al termine della $1$-a modifica, durante la maratona avvengono $967009272178$ collisioni. Pertanto, il resto della divisione per $1000000007$ del numero di collisioni che avvengono durante la maratona è $9265409$.

Questo esempio di input soddisfa le assunzioni dei Subtask $2, 3, 4, 5, 6$.

Esempio 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

Spiegazione

Questo esempio di input soddisfa le assunzioni dei Subtask $3, 5, 6$.