Uppgiftsbeskrivning

Bitaro bor runt en stor cirkelformad sjö. Sjöns omkrets är $L$, och vid en viss punkt längs sjöns strand ligger Bitaros hus. Den punkt man når genom att förflytta sig sträckan $x$ ($0 \le x < L$) medurs längs sjöns strand från Bitaros hus kallas punkt $x$. För närvarande planeras ett maratonlopp som ska hållas runt sjön.

Bitaro har hört att maratonloppet planeras att genomföras på följande sätt:

• Nummerlappar numrerade från $0$ till $L - 1$ har förberetts, $1$ av varje. Varje deltagare i maratonloppet bär en av nummerlapparna. Startpunkten för deltagaren som bär nummerlapp $l$ ($0 \le l \le L - 1$) är punkt $l$.
• Efter att maratonloppet har startat förflyttar sig deltagarna under $T$ sekunder medurs runt sjön med sina respektive hastigheter. Det ögonblick då $t$ sekunder ($0 \le t \le T$) har förflutit sedan maratonloppets start kallas tidpunkt $t$.

Bitaro har deltagarlistan för maratonloppet. För närvarande finns $N$ deltagare upptagna på deltagarlistan, och den $i$:te deltagaren ($1 \le i \le N$) planeras bära nummerlapp $A_i$ och förflytta sig medurs runt sjön med hastigheten $S_i$ per $1$ sekund.

Utifrån deltagarlistan beräknade Bitaro antalet kollisioner som inträffar under maratonloppet. Här avser en kollision att $2$ olika deltagare befinner sig i samma punkt. Strikt talat fann han antalet tripplar $(p, q, t)$ bestående av heltal $p, q$ som uppfyller $0 \le p < q \le L - 1$ och ett reellt tal $t$ som uppfyller $0 \le t \le T$ vilka uppfyller följande villkor:

• Det finns en deltagare som bär nummerlapp $p$.
• Det finns en deltagare som bär nummerlapp $q$.
• Deltagaren som bär nummerlapp $p$ och deltagaren som bär nummerlapp $q$ befinner sig i samma punkt vid tidpunkt $t$.

Därefter gjordes dock $Q$ ändringar i deltagarlistan. Den $j$:te ändringen ($1 \le j \le Q$) representeras av $2$ heltal $X_j, Y_j$ och innebär följande:

• Om det för närvarande finns en person på deltagarlistan som bär nummerlapp $X_j$ och förflyttar sig medurs runt sjön med hastigheten $Y_j$ per $1$ sekund, tas denna person bort från deltagarlistan. Annars läggs en ny person som bär nummerlapp $X_j$ och förflyttar sig medurs runt sjön med hastigheten $Y_j$ per $1$ sekund till på deltagarlistan.

Det garanteras dock att det vid tidpunkten då vilken ändring som helst är klar finns minst $2$ deltagare upptagna på deltagarlistan, samt att nummerlapparna som deltagarna bär är parvis olika.

Bitaro vill för deltagarna vid tidpunkten då varje ändring är klar veta antalet kollisioner som inträffar under maratonloppet. Utifrån begränsningarna i uppgiften kan det bevisas att antalet kollisioner som inträffar under maratonloppet är ändligt.

Givet informationen om maratonloppet och ändringarna i deltagarlistan, skriv ett program som för deltagarna vid tidpunkten då varje ändring är klar beräknar resten då antalet kollisioner som inträffar under maratonloppet divideras med $1000000007$.

Begränsningar

• $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$).
• Vid tidpunkten då vilken ändring som helst är klar finns det minst $2$ deltagare.
• Vid tidpunkten då vilken ändring som helst är klar är deltagarnas startpunkter parvis olika.
• Alla indatavärden är heltal.

Deluppgifter

1. ($10$ poäng) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ poäng) $N \le 2000$, $Q = 1$.
3. ($11$ poäng) $N \le 2000$, $Q \le 2000$.
4. ($27$ poäng) $Q = 1$.
5. ($34$ poäng) $N + Q \le 78000$.
6. ($10$ poäng) Inga ytterligare begränsningar.

Indata

Indata ges på följande 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}$$

Utdata

Skriv ut $Q$ rader. På den $j$:te raden ($1 \le j \le Q$) ska du skriva ut resten då antalet kollisioner som inträffar under maratonloppet bland deltagarna vid tidpunkten då den $j$:te ändringen är klar divideras med $1000000007$.

Exempel

Exempel 1

Indata

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

Utdata

7

Förklaring

Det finns $4$ deltagare vid tidpunkten då den $1$:a ändringen är klar. Informationen om varje deltagare är som följer:

1. Bär nummerlapp $1$ och startar från punkt $1$. Förflyttar sig medurs med hastigheten $4$ per $1$ sekund.
2. Bär nummerlapp $6$ och startar från punkt $6$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
3. Bär nummerlapp $3$ och startar från punkt $3$. Förflyttar sig medurs med hastigheten $6$ per $1$ sekund.
4. Bär nummerlapp $4$ och startar från punkt $4$. Förflyttar sig medurs med hastigheten $2$ per $1$ sekund.

Bland deltagarna vid tidpunkten då den $1$:a ändringen är klar inträffar följande $7$ kollisioner under maratonloppet:

1. Vid tidpunkt $1 \div 4$ befinner sig deltagaren med nummerlapp $3$ och deltagaren med nummerlapp $4$ i samma punkt $9 \div 2$.
2. Vid tidpunkt $3 \div 5$ befinner sig deltagaren med nummerlapp $3$ och deltagaren med nummerlapp $6$ i samma punkt $33 \div 5$.
3. Vid tidpunkt $3 \div 2$ befinner sig deltagaren med nummerlapp $1$ och deltagaren med nummerlapp $4$ i samma punkt $0$.
4. Vid tidpunkt $5 \div 3$ befinner sig deltagaren med nummerlapp $1$ och deltagaren med nummerlapp $6$ i samma punkt $2 \div 3$.
5. Vid tidpunkt $2$ befinner sig deltagaren med nummerlapp $3$ och deltagaren med nummerlapp $4$ i samma punkt $1$.
6. Vid tidpunkt $2$ befinner sig deltagaren med nummerlapp $3$ och deltagaren med nummerlapp $6$ i samma punkt $1$.
7. Vid tidpunkt $2$ befinner sig deltagaren med nummerlapp $4$ och deltagaren med nummerlapp $6$ i samma punkt $1$.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4, 5, 6$.

Exempel 2

Indata

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

Utdata

1
0

Förklaring

Det finns $4$ deltagare vid tidpunkten då den $1$:a ändringen är klar. Informationen om varje deltagare är som följer:

1. Bär nummerlapp $1$ och startar från punkt $1$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
2. Bär nummerlapp $3$ och startar från punkt $3$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
3. Bär nummerlapp $4$ och startar från punkt $4$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
4. Bär nummerlapp $0$ och startar från punkt $0$. Förflyttar sig medurs med hastigheten $2$ per $1$ sekund.

Bland deltagarna vid tidpunkten då den $1$:a ändringen är klar inträffar följande $1$ kollision under maratonloppet:

1. Vid tidpunkt $1$ befinner sig deltagaren med nummerlapp $0$ och deltagaren med nummerlapp $1$ i samma punkt $2$.

Det finns $3$ deltagare vid tidpunkten då den $2$:a ändringen är klar. Informationen om varje deltagare är som följer:

1. Bär nummerlapp $3$ och startar från punkt $3$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
2. Bär nummerlapp $4$ och startar från punkt $4$. Förflyttar sig medurs med hastigheten $1$ per $1$ sekund.
3. Bär nummerlapp $0$ och startar från punkt $0$. Förflyttar sig medurs med hastigheten $2$ per $1$ sekund.

Bland deltagarna vid tidpunkten då den $2$:a ändringen är klar inträffar $0$ kollisioner under maratonloppet.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $1, 3, 5, 6$.

Exempel 3

Indata

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Utdata

9265409

Förklaring

Det finns $3$ deltagare vid tidpunkten då den $1$:a ändringen är klar. Informationen om varje deltagare är som följer:

1. Bär nummerlapp $58683$ och startar från punkt $58683$. Förflyttar sig medurs med hastigheten $28489$ per $1$ sekund.
2. Bär nummerlapp $3478$ och startar från punkt $3478$. Förflyttar sig medurs med hastigheten $48682814$ per $1$ sekund.
3. Bär nummerlapp $28482$ och startar från punkt $28482$. Förflyttar sig medurs med hastigheten $39599461$ per $1$ sekund.

Bland deltagarna vid tidpunkten då den $1$:a ändringen är klar inträffar $967009272178$ kollisioner under maratonloppet. Därför är resten då antalet kollisioner som inträffar under maratonloppet divideras med $1000000007$ lika med $9265409$.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $2, 3, 4, 5, 6$.

Exempel 4

Indata

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

Utdata

330
264
341
440
341

Förklaring

Detta indataexempel uppfyller begränsningarna för deluppgifterna $3, 5, 6$.