Tehtävänanto

Bitaro asuu suuren ympyränmuotoisen järven ympärillä. Järven ympärysmitta on $L$, ja eräässä kohdassa järven rannalla sijaitsee Bitaron talo. Kohtaa, johon päädytään kulkemalla Bitaron talolta järven rantaa pitkin myötäpäivään matka $x$ ($0 \le x < L$), kutsutaan pisteeksi $x$. Parhaillaan suunnitellaan järven ympäri juostavaa maratonkilpailua.

Bitaro kuuli, että maratonkilpailu on tarkoitus järjestää seuraavasti:

• Numerolappuja, jotka on numeroitu $0$:sta $L - 1$:een, on varattu $1$ kappale kutakin. Jokainen maratonkilpailun osallistuja käyttää yhtä numerolappua. Numerolappua $l$ ($0 \le l \le L - 1$) käyttävän osallistujan lähtöpiste on piste $l$.
• Kun maratonkilpailu on alkanut, osallistujat kulkevat $T$ sekunnin ajan myötäpäivään järven ympäri kukin omalla nopeudellaan. Ajanhetkeä, jolloin maratonkilpailun alusta on kulunut $t$ sekuntia ($0 \le t \le T$), kutsutaan ajanhetkeksi $t$.

Bitarolla on maratonkilpailun osallistujaluettelo. Tällä hetkellä osallistujaluetteloon on merkitty $N$ osallistujaa, ja $i$:nnen osallistujan ($1 \le i \le N$) on määrä käyttää numerolappua $A_i$ ja kulkea myötäpäivään järven ympäri nopeudella $S_i$ jokaista $1$ sekuntia kohti.

Osallistujaluettelon perusteella Bitaro laski maratonkilpailun aikana tapahtuvien törmäysten lukumäärän. Tässä törmäyksellä tarkoitetaan sitä, että $2$ eri osallistujaa on samassa pisteessä. Täsmällisesti sanottuna hän etsi sellaisten kolmikoiden $(p, q, t)$ lukumäärän, jotka koostuvat ehdon $0 \le p < q \le L - 1$ täyttävistä kokonaisluvuista $p, q$ sekä ehdon $0 \le t \le T$ täyttävästä reaaliluvusta $t$ ja jotka täyttävät seuraavat ehdot:

• On olemassa osallistuja, joka käyttää numerolappua $p$.
• On olemassa osallistuja, joka käyttää numerolappua $q$.
• Numerolappua $p$ käyttävä osallistuja ja numerolappua $q$ käyttävä osallistuja ovat samassa pisteessä ajanhetkellä $t$.

Tämän jälkeen osallistujaluetteloon tehtiin kuitenkin $Q$ muutosta. $j$:ttä muutosta ($1 \le j \le Q$) kuvaa $2$ kokonaislukua $X_j, Y_j$, ja se on seuraavanlainen:

• Jos osallistujaluetteloon on tällä hetkellä merkitty henkilö, joka käyttää numerolappua $X_j$ ja kulkee myötäpäivään järven ympäri nopeudella $Y_j$ jokaista $1$ sekuntia kohti, tämä henkilö poistetaan osallistujaluettelosta. Muussa tapauksessa osallistujaluetteloon lisätään uutena henkilö, joka käyttää numerolappua $X_j$ ja kulkee myötäpäivään järven ympäri nopeudella $Y_j$ jokaista $1$ sekuntia kohti.

On kuitenkin taattu, että minkä tahansa muutoksen päättyessä osallistujaluetteloon on merkitty vähintään $2$ osallistujaa ja että osallistujien käyttämät numerolaput ovat keskenään eri suuria.

Bitaro haluaa tietää kunkin muutoksen päättymishetken osallistujille, kuinka monta törmäystä maratonkilpailun aikana tapahtuu. Tehtävänannon rajoitusten perusteella voidaan todistaa, että maratonkilpailun aikana tapahtuvien törmäysten lukumäärä on äärellinen.

Kun maratonkilpailun tiedot ja osallistujaluetteloon tehtävät muutokset annetaan, kirjoita ohjelma, joka laskee kunkin muutoksen päättymishetken osallistujille jakojäännöksen, kun maratonkilpailun aikana tapahtuvien törmäysten lukumäärä jaetaan luvulla $1000000007$.

Rajoitukset

• $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$).
• Minkä tahansa muutoksen päättyessä osallistujia on vähintään $2$.
• Minkä tahansa muutoksen päättyessä osallistujien lähtöpisteet ovat keskenään eri pisteitä.
• Kaikki syötteen arvot ovat kokonaislukuja.

Osatehtävät

1. ($10$ pistettä) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ pistettä) $N \le 2000$, $Q = 1$.
3. ($11$ pistettä) $N \le 2000$, $Q \le 2000$.
4. ($27$ pistettä) $Q = 1$.
5. ($34$ pistettä) $N + Q \le 78000$.
6. ($10$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan seuraavassa muodossa: $$\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}$$

Tuloste

Tulosta $Q$ riviä. Tulosta $j$:nnelle riville ($1 \le j \le Q$) jakojäännös, kun $j$:nnen muutoksen päättymishetken osallistujien kesken maratonkilpailun aikana tapahtuvien törmäysten lukumäärä jaetaan luvulla $1000000007$.

Esimerkki

Esimerkki 1

Syöte

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

Tuloste

7

Selitys

$1$. muutoksen päättyessä osallistujia on $4$. Kunkin osallistujan tiedot ovat seuraavat:

1. Käyttää numerolappua $1$ ja lähtee pisteestä $1$. Kulkee myötäpäivään nopeudella $4$ jokaista $1$ sekuntia kohti.
2. Käyttää numerolappua $6$ ja lähtee pisteestä $6$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
3. Käyttää numerolappua $3$ ja lähtee pisteestä $3$. Kulkee myötäpäivään nopeudella $6$ jokaista $1$ sekuntia kohti.
4. Käyttää numerolappua $4$ ja lähtee pisteestä $4$. Kulkee myötäpäivään nopeudella $2$ jokaista $1$ sekuntia kohti.

$1$. muutoksen päättymishetken osallistujien kesken maratonkilpailun aikana tapahtuu seuraavat $7$ törmäystä:

1. Ajanhetkellä $1 \div 4$ numerolappua $3$ käyttävä osallistuja ja numerolappua $4$ käyttävä osallistuja ovat samassa pisteessä $9 \div 2$.
2. Ajanhetkellä $3 \div 5$ numerolappua $3$ käyttävä osallistuja ja numerolappua $6$ käyttävä osallistuja ovat samassa pisteessä $33 \div 5$.
3. Ajanhetkellä $3 \div 2$ numerolappua $1$ käyttävä osallistuja ja numerolappua $4$ käyttävä osallistuja ovat samassa pisteessä $0$.
4. Ajanhetkellä $5 \div 3$ numerolappua $1$ käyttävä osallistuja ja numerolappua $6$ käyttävä osallistuja ovat samassa pisteessä $2 \div 3$.
5. Ajanhetkellä $2$ numerolappua $3$ käyttävä osallistuja ja numerolappua $4$ käyttävä osallistuja ovat samassa pisteessä $1$.
6. Ajanhetkellä $2$ numerolappua $3$ käyttävä osallistuja ja numerolappua $6$ käyttävä osallistuja ovat samassa pisteessä $1$.
7. Ajanhetkellä $2$ numerolappua $4$ käyttävä osallistuja ja numerolappua $6$ käyttävä osallistuja ovat samassa pisteessä $1$.

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkki 2

Syöte

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

Tuloste

1
0

Selitys

$1$. muutoksen päättyessä osallistujia on $4$. Kunkin osallistujan tiedot ovat seuraavat:

1. Käyttää numerolappua $1$ ja lähtee pisteestä $1$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
2. Käyttää numerolappua $3$ ja lähtee pisteestä $3$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
3. Käyttää numerolappua $4$ ja lähtee pisteestä $4$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
4. Käyttää numerolappua $0$ ja lähtee pisteestä $0$. Kulkee myötäpäivään nopeudella $2$ jokaista $1$ sekuntia kohti.

$1$. muutoksen päättymishetken osallistujien kesken maratonkilpailun aikana tapahtuu seuraava $1$ törmäys:

1. Ajanhetkellä $1$ numerolappua $0$ käyttävä osallistuja ja numerolappua $1$ käyttävä osallistuja ovat samassa pisteessä $2$.

$2$. muutoksen päättyessä osallistujia on $3$. Kunkin osallistujan tiedot ovat seuraavat:

1. Käyttää numerolappua $3$ ja lähtee pisteestä $3$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
2. Käyttää numerolappua $4$ ja lähtee pisteestä $4$. Kulkee myötäpäivään nopeudella $1$ jokaista $1$ sekuntia kohti.
3. Käyttää numerolappua $0$ ja lähtee pisteestä $0$. Kulkee myötäpäivään nopeudella $2$ jokaista $1$ sekuntia kohti.

$2$. muutoksen päättymishetken osallistujien kesken maratonkilpailun aikana tapahtuu $0$ törmäystä.

Tämä syöteesimerkki täyttää osatehtävien $1, 3, 5, 6$ rajoitukset.

Esimerkki 3

Syöte

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Tuloste

9265409

Selitys

$1$. muutoksen päättyessä osallistujia on $3$. Kunkin osallistujan tiedot ovat seuraavat:

1. Käyttää numerolappua $58683$ ja lähtee pisteestä $58683$. Kulkee myötäpäivään nopeudella $28489$ jokaista $1$ sekuntia kohti.
2. Käyttää numerolappua $3478$ ja lähtee pisteestä $3478$. Kulkee myötäpäivään nopeudella $48682814$ jokaista $1$ sekuntia kohti.
3. Käyttää numerolappua $28482$ ja lähtee pisteestä $28482$. Kulkee myötäpäivään nopeudella $39599461$ jokaista $1$ sekuntia kohti.

$1$. muutoksen päättymishetken osallistujien kesken maratonkilpailun aikana tapahtuu $967009272178$ törmäystä. Näin ollen maratonkilpailun aikana tapahtuvien törmäysten lukumäärän jakojäännös jaettaessa luvulla $1000000007$ on $9265409$.

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkki 4

Syöte

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

Tuloste

330
264
341
440
341

Selitys

Tämä syöteesimerkki täyttää osatehtävien $3, 5, 6$ rajoitukset.