Oppgavebeskrivelse

Bitaro bor rundt en stor sirkelformet innsjø. Omkretsen av innsjøen er $L$, og ved et bestemt punkt langs bredden av innsjøen ligger huset til Bitaro. Punktet man kommer til ved å bevege seg en avstand $x$ ($0 \le x < L$) med urviseren langs bredden av innsjøen fra Bitaros hus, kalles punkt $x$. For tiden planlegges det et maratonløp som skal arrangeres rundt innsjøen.

Bitaro har hørt at maratonløpet etter planen skal gjennomføres på følgende måte:

• Det er gjort klart startnumre nummerert fra $0$ til $L - 1$, $1$ av hvert. Hver deltaker i maratonløpet bærer ett av startnumrene. Startpunktet for deltakeren som bærer startnummer $l$ ($0 \le l \le L - 1$), er punkt $l$.
• Etter at maratonløpet har startet, beveger deltakerne seg i $T$ sekunder med urviseren rundt innsjøen med sine respektive hastigheter. Tidspunktet når det har gått $t$ sekunder ($0 \le t \le T$) siden starten av maratonløpet, kalles tidspunkt $t$.

Bitaro har deltakerlisten for maratonløpet. For øyeblikket står $N$ deltakere oppført på deltakerlisten, og den $i$-te deltakeren ($1 \le i \le N$) skal etter planen bære startnummer $A_i$ og bevege seg med urviseren rundt innsjøen med en hastighet på $S_i$ per $1$ sekund.

Basert på deltakerlisten fant Bitaro antallet kollisjoner som skjer i løpet av maratonløpet. Her betyr en kollisjon at $2$ forskjellige deltakere befinner seg i samme punkt. Strengt tatt fant han antallet tripler $(p, q, t)$ bestående av heltall $p, q$ som oppfyller $0 \le p < q \le L - 1$ og et reelt tall $t$ som oppfyller $0 \le t \le T$, som tilfredsstiller følgende betingelser:

• Det finnes en deltaker som bærer startnummer $p$.
• Det finnes en deltaker som bærer startnummer $q$.
• Deltakeren som bærer startnummer $p$, og deltakeren som bærer startnummer $q$, befinner seg i samme punkt ved tidspunkt $t$.

Etter dette ble det imidlertid gjort $Q$ endringer i deltakerlisten. Den $j$-te endringen ($1 \le j \le Q$) representeres ved $2$ heltall $X_j, Y_j$, og er som følger:

• Hvis det for øyeblikket står oppført en person på deltakerlisten som bærer startnummer $X_j$ og beveger seg med urviseren rundt innsjøen med en hastighet på $Y_j$ per $1$ sekund, fjernes denne personen fra deltakerlisten. Ellers legges det til en ny person på deltakerlisten som bærer startnummer $X_j$ og beveger seg med urviseren rundt innsjøen med en hastighet på $Y_j$ per $1$ sekund.

Det er imidlertid garantert at det ved tidspunktet når en hvilken som helst endring er fullført, står minst $2$ deltakere oppført på deltakerlisten, og at startnumrene som deltakerne bærer, er parvis forskjellige.

Bitaro ønsker å vite, for deltakerne ved tidspunktet når hver endring er fullført, hvor mange kollisjoner som skjer i løpet av maratonløpet. Ut fra begrensningene i oppgaveteksten kan det bevises at antallet kollisjoner som skjer i løpet av maratonløpet, er endelig.

Gitt informasjonen om maratonløpet og endringene i deltakerlisten, skriv et program som for deltakerne ved tidspunktet når hver endring er fullført, finner resten når antallet kollisjoner som skjer i løpet av maratonløpet, deles på $1000000007$.

Begrensninger

• $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$).
• Ved tidspunktet når en hvilken som helst endring er fullført, er det minst $2$ deltakere.
• Ved tidspunktet når en hvilken som helst endring er fullført, er deltakernes startpunkter parvis forskjellige.
• Alle inndataverdier er heltall.

Deloppgaver

1. ($10$ poeng) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ poeng) $N \le 2000$, $Q = 1$.
3. ($11$ poeng) $N \le 2000$, $Q \le 2000$.
4. ($27$ poeng) $Q = 1$.
5. ($34$ poeng) $N + Q \le 78000$.
6. ($10$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndataene gis på følgende 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$ linjer. På den $j$-te linjen ($1 \le j \le Q$) skal du skrive ut resten når antallet kollisjoner som skjer i løpet av maratonløpet blant deltakerne ved tidspunktet når den $j$-te endringen er fullført, deles på $1000000007$.

Eksempel

Eksempel 1

Inndata

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

Utdata

7

Forklaring

Det er $4$ deltakere ved tidspunktet når den $1$. endringen er fullført. Informasjonen om hver deltaker er som følger:

1. Bærer startnummer $1$ og starter fra punkt $1$. Beveger seg med urviseren med en hastighet på $4$ per $1$ sekund.
2. Bærer startnummer $6$ og starter fra punkt $6$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
3. Bærer startnummer $3$ og starter fra punkt $3$. Beveger seg med urviseren med en hastighet på $6$ per $1$ sekund.
4. Bærer startnummer $4$ og starter fra punkt $4$. Beveger seg med urviseren med en hastighet på $2$ per $1$ sekund.

Blant deltakerne ved tidspunktet når den $1$. endringen er fullført, skjer følgende $7$ kollisjoner i løpet av maratonløpet:

1. Ved tidspunkt $1 \div 4$ befinner deltakeren med startnummer $3$ og deltakeren med startnummer $4$ seg i samme punkt $9 \div 2$.
2. Ved tidspunkt $3 \div 5$ befinner deltakeren med startnummer $3$ og deltakeren med startnummer $6$ seg i samme punkt $33 \div 5$.
3. Ved tidspunkt $3 \div 2$ befinner deltakeren med startnummer $1$ og deltakeren med startnummer $4$ seg i samme punkt $0$.
4. Ved tidspunkt $5 \div 3$ befinner deltakeren med startnummer $1$ og deltakeren med startnummer $6$ seg i samme punkt $2 \div 3$.
5. Ved tidspunkt $2$ befinner deltakeren med startnummer $3$ og deltakeren med startnummer $4$ seg i samme punkt $1$.
6. Ved tidspunkt $2$ befinner deltakeren med startnummer $3$ og deltakeren med startnummer $6$ seg i samme punkt $1$.
7. Ved tidspunkt $2$ befinner deltakeren med startnummer $4$ og deltakeren med startnummer $6$ seg i samme punkt $1$.

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 3, 4, 5, 6$.

Eksempel 2

Inndata

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

Utdata

1
0

Forklaring

Det er $4$ deltakere ved tidspunktet når den $1$. endringen er fullført. Informasjonen om hver deltaker er som følger:

1. Bærer startnummer $1$ og starter fra punkt $1$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
2. Bærer startnummer $3$ og starter fra punkt $3$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
3. Bærer startnummer $4$ og starter fra punkt $4$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
4. Bærer startnummer $0$ og starter fra punkt $0$. Beveger seg med urviseren med en hastighet på $2$ per $1$ sekund.

Blant deltakerne ved tidspunktet når den $1$. endringen er fullført, skjer følgende $1$ kollisjon i løpet av maratonløpet:

1. Ved tidspunkt $1$ befinner deltakeren med startnummer $0$ og deltakeren med startnummer $1$ seg i samme punkt $2$.

Det er $3$ deltakere ved tidspunktet når den $2$. endringen er fullført. Informasjonen om hver deltaker er som følger:

1. Bærer startnummer $3$ og starter fra punkt $3$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
2. Bærer startnummer $4$ og starter fra punkt $4$. Beveger seg med urviseren med en hastighet på $1$ per $1$ sekund.
3. Bærer startnummer $0$ og starter fra punkt $0$. Beveger seg med urviseren med en hastighet på $2$ per $1$ sekund.

Blant deltakerne ved tidspunktet når den $2$. endringen er fullført, skjer det $0$ kollisjoner i løpet av maratonløpet.

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $1, 3, 5, 6$.

Eksempel 3

Inndata

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Utdata

9265409

Forklaring

Det er $3$ deltakere ved tidspunktet når den $1$. endringen er fullført. Informasjonen om hver deltaker er som følger:

1. Bærer startnummer $58683$ og starter fra punkt $58683$. Beveger seg med urviseren med en hastighet på $28489$ per $1$ sekund.
2. Bærer startnummer $3478$ og starter fra punkt $3478$. Beveger seg med urviseren med en hastighet på $48682814$ per $1$ sekund.
3. Bærer startnummer $28482$ og starter fra punkt $28482$. Beveger seg med urviseren med en hastighet på $39599461$ per $1$ sekund.

Blant deltakerne ved tidspunktet når den $1$. endringen er fullført, skjer det $967009272178$ kollisjoner i løpet av maratonløpet. Derfor er resten når antallet kollisjoner som skjer i løpet av maratonløpet, deles på $1000000007$, lik $9265409$.

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $2, 3, 4, 5, 6$.

Eksempel 4

Inndata

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

Forklaring

Dette inndataeksempelet oppfyller begrensningene i deloppgavene $3, 5, 6$.