Problembeschreibung

Bitaro lebt am Ufer eines großen kreisförmigen Sees. Der Umfang des Sees beträgt $L$, und an einer bestimmten Stelle am Seeufer steht Bitaros Haus. Der Punkt, den man erreicht, wenn man sich von Bitaros Haus aus um $x$ ($0 \le x < L$) im Uhrzeigersinn entlang des Seeufers bewegt, wird Punkt $x$ genannt. Derzeit wird ein Marathonlauf geplant, der rund um den See stattfinden soll.

Bitaro hat gehört, dass der Marathonlauf wie folgt ablaufen soll:

• Es werden Startnummern von $0$ bis $L - 1$ vorbereitet, jeweils $1$ Stück. Jeder Teilnehmer des Marathonlaufs trägt eine dieser Startnummern. Der Startpunkt des Teilnehmers mit der Startnummer $l$ ($0 \le l \le L - 1$) ist der Punkt $l$.
• Nach dem Start des Marathonlaufs bewegen sich die Teilnehmer $T$ Sekunden lang mit ihrer jeweiligen Geschwindigkeit im Uhrzeigersinn um den See. Der Zeitpunkt, zu dem seit dem Start des Marathonlaufs $t$ Sekunden ($0 \le t \le T$) vergangen sind, wird Zeitpunkt $t$ genannt.

Bitaro besitzt die Teilnehmerliste des Marathonlaufs. Derzeit stehen $N$ Teilnehmer auf der Teilnehmerliste, und der $i$-te Teilnehmer ($1 \le i \le N$) soll die Startnummer $A_i$ tragen und sich mit einer Geschwindigkeit von $S_i$ pro $1$ Sekunde im Uhrzeigersinn um den See bewegen.

Anhand der Teilnehmerliste hat Bitaro die Anzahl der Kollisionen ermittelt, die während des Marathonlaufs auftreten. Hierbei bezeichnet eine Kollision den Umstand, dass sich $2$ verschiedene Teilnehmer am selben Punkt befinden. Genaugenommen hat er die Anzahl der Tripel $(p, q, t)$ bestehend aus ganzen Zahlen $p, q$ mit $0 \le p < q \le L - 1$ und einer reellen Zahl $t$ mit $0 \le t \le T$ bestimmt, die die folgenden Bedingungen erfüllen:

• Es gibt einen Teilnehmer, der die Startnummer $p$ trägt.
• Es gibt einen Teilnehmer, der die Startnummer $q$ trägt.
• Der Teilnehmer mit der Startnummer $p$ und der Teilnehmer mit der Startnummer $q$ befinden sich zum Zeitpunkt $t$ am selben Punkt.

Danach wurden jedoch $Q$ Änderungen an der Teilnehmerliste vorgenommen. Die $j$-te Änderung ($1 \le j \le Q$) wird durch $2$ ganze Zahlen $X_j, Y_j$ dargestellt und sieht wie folgt aus:

• Falls derzeit eine Person auf der Teilnehmerliste steht, die die Startnummer $X_j$ trägt und sich mit einer Geschwindigkeit von $Y_j$ pro $1$ Sekunde im Uhrzeigersinn um den See bewegt, wird diese Person von der Teilnehmerliste gestrichen. Andernfalls wird eine Person, die die Startnummer $X_j$ trägt und sich mit einer Geschwindigkeit von $Y_j$ pro $1$ Sekunde im Uhrzeigersinn um den See bewegt, neu zur Teilnehmerliste hinzugefügt.

Es ist jedoch garantiert, dass nach Abschluss jeder Änderung mindestens $2$ Teilnehmer auf der Teilnehmerliste stehen und die von den Teilnehmern getragenen Startnummern paarweise verschieden sind.

Bitaro möchte für die Teilnehmer zum Zeitpunkt nach Abschluss jeder einzelnen Änderung wissen, wie viele Kollisionen während des Marathonlaufs auftreten. Aus den Bedingungen der Aufgabenstellung lässt sich beweisen, dass die Anzahl der während des Marathonlaufs auftretenden Kollisionen endlich ist.

Schreibe ein Programm, das anhand der Informationen über den Marathonlauf und die Änderungen an der Teilnehmerliste für die Teilnehmer nach Abschluss jeder Änderung den Rest berechnet, der bei der Division der Anzahl der während des Marathonlaufs auftretenden Kollisionen durch $1000000007$ bleibt.

Bedingungen

• $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$).
• Nach Abschluss jeder Änderung gibt es mindestens $2$ Teilnehmer.
• Nach Abschluss jeder Änderung sind die Startpunkte der Teilnehmer paarweise verschieden.
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($10$ Punkte) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ Punkte) $N \le 2000$, $Q = 1$.
3. ($11$ Punkte) $N \le 2000$, $Q \le 2000$.
4. ($27$ Punkte) $Q = 1$.
5. ($34$ Punkte) $N + Q \le 78000$.
6. ($10$ Punkte) Keine zusätzlichen Bedingungen.

Eingabe

Die Eingabe erfolgt im folgenden 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}$$

Ausgabe

Gib $Q$ Zeilen aus. Gib in der $j$-ten Zeile ($1 \le j \le Q$) den Rest aus, der bei der Division der Anzahl der während des Marathonlaufs auftretenden Kollisionen unter den Teilnehmern nach Abschluss der $j$-ten Änderung durch $1000000007$ bleibt.

Beispiel

Beispiel 1

Eingabe

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

Ausgabe

7

Erklärung

Nach Abschluss der $1$. Änderung gibt es $4$ Teilnehmer. Die Informationen zu den einzelnen Teilnehmern lauten wie folgt:

1. Trägt Startnummer $1$ und startet bei Punkt $1$. Bewegt sich mit einer Geschwindigkeit von $4$ pro $1$ Sekunde im Uhrzeigersinn.
2. Trägt Startnummer $6$ und startet bei Punkt $6$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
3. Trägt Startnummer $3$ und startet bei Punkt $3$. Bewegt sich mit einer Geschwindigkeit von $6$ pro $1$ Sekunde im Uhrzeigersinn.
4. Trägt Startnummer $4$ und startet bei Punkt $4$. Bewegt sich mit einer Geschwindigkeit von $2$ pro $1$ Sekunde im Uhrzeigersinn.

Unter den Teilnehmern nach Abschluss der $1$. Änderung treten während des Marathonlaufs die folgenden $7$ Kollisionen auf:

1. Zum Zeitpunkt $1 \div 4$ befinden sich der Teilnehmer mit Startnummer $3$ und der Teilnehmer mit Startnummer $4$ am selben Punkt $9 \div 2$.
2. Zum Zeitpunkt $3 \div 5$ befinden sich der Teilnehmer mit Startnummer $3$ und der Teilnehmer mit Startnummer $6$ am selben Punkt $33 \div 5$.
3. Zum Zeitpunkt $3 \div 2$ befinden sich der Teilnehmer mit Startnummer $1$ und der Teilnehmer mit Startnummer $4$ am selben Punkt $0$.
4. Zum Zeitpunkt $5 \div 3$ befinden sich der Teilnehmer mit Startnummer $1$ und der Teilnehmer mit Startnummer $6$ am selben Punkt $2 \div 3$.
5. Zum Zeitpunkt $2$ befinden sich der Teilnehmer mit Startnummer $3$ und der Teilnehmer mit Startnummer $4$ am selben Punkt $1$.
6. Zum Zeitpunkt $2$ befinden sich der Teilnehmer mit Startnummer $3$ und der Teilnehmer mit Startnummer $6$ am selben Punkt $1$.
7. Zum Zeitpunkt $2$ befinden sich der Teilnehmer mit Startnummer $4$ und der Teilnehmer mit Startnummer $6$ am selben Punkt $1$.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 4, 5, 6$.

Beispiel 2

Eingabe

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

Ausgabe

1
0

Erklärung

Nach Abschluss der $1$. Änderung gibt es $4$ Teilnehmer. Die Informationen zu den einzelnen Teilnehmern lauten wie folgt:

1. Trägt Startnummer $1$ und startet bei Punkt $1$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
2. Trägt Startnummer $3$ und startet bei Punkt $3$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
3. Trägt Startnummer $4$ und startet bei Punkt $4$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
4. Trägt Startnummer $0$ und startet bei Punkt $0$. Bewegt sich mit einer Geschwindigkeit von $2$ pro $1$ Sekunde im Uhrzeigersinn.

Unter den Teilnehmern nach Abschluss der $1$. Änderung tritt während des Marathonlaufs die folgende $1$ Kollision auf:

1. Zum Zeitpunkt $1$ befinden sich der Teilnehmer mit Startnummer $0$ und der Teilnehmer mit Startnummer $1$ am selben Punkt $2$.

Nach Abschluss der $2$. Änderung gibt es $3$ Teilnehmer. Die Informationen zu den einzelnen Teilnehmern lauten wie folgt:

1. Trägt Startnummer $3$ und startet bei Punkt $3$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
2. Trägt Startnummer $4$ und startet bei Punkt $4$. Bewegt sich mit einer Geschwindigkeit von $1$ pro $1$ Sekunde im Uhrzeigersinn.
3. Trägt Startnummer $0$ und startet bei Punkt $0$. Bewegt sich mit einer Geschwindigkeit von $2$ pro $1$ Sekunde im Uhrzeigersinn.

Unter den Teilnehmern nach Abschluss der $2$. Änderung treten während des Marathonlaufs $0$ Kollisionen auf.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $1, 3, 5, 6$.

Beispiel 3

Eingabe

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Ausgabe

9265409

Erklärung

Nach Abschluss der $1$. Änderung gibt es $3$ Teilnehmer. Die Informationen zu den einzelnen Teilnehmern lauten wie folgt:

1. Trägt Startnummer $58683$ und startet bei Punkt $58683$. Bewegt sich mit einer Geschwindigkeit von $28489$ pro $1$ Sekunde im Uhrzeigersinn.
2. Trägt Startnummer $3478$ und startet bei Punkt $3478$. Bewegt sich mit einer Geschwindigkeit von $48682814$ pro $1$ Sekunde im Uhrzeigersinn.
3. Trägt Startnummer $28482$ und startet bei Punkt $28482$. Bewegt sich mit einer Geschwindigkeit von $39599461$ pro $1$ Sekunde im Uhrzeigersinn.

Unter den Teilnehmern nach Abschluss der $1$. Änderung treten während des Marathonlaufs $967009272178$ Kollisionen auf. Daher beträgt der Rest bei der Division der Anzahl der während des Marathonlaufs auftretenden Kollisionen durch $1000000007$ gleich $9265409$.

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $2, 3, 4, 5, 6$.

Beispiel 4

Eingabe

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

Ausgabe

330
264
341
440
341

Erklärung

Dieses Eingabebeispiel erfüllt die Bedingungen der Teilaufgaben $3, 5, 6$.