Lýsing á verkefni

Bitaro býr við stórt hringlaga stöðuvatn. Ummál vatnsins er $L$, og á ákveðnum stað við vatnsbakkann stendur hús Bitaro. Staðurinn sem komið er á með því að ferðast vegalengdina $x$ ($0 \le x < L$) réttsælis meðfram vatnsbakkanum frá húsi Bitaro kallast punktur $x$. Nú stendur yfir undirbúningur fyrir maraþonhlaup sem haldið verður í kringum vatnið.

Bitaro heyrði að maraþonhlaupið ætti að fara fram á eftirfarandi hátt:

• Keppnisnúmer merkt frá $0$ til $L - 1$ eru tilbúin, $1$ af hverju. Hver þátttakandi í maraþonhlaupinu ber eitt af keppnisnúmerunum. Upphafsstaður þátttakandans sem ber keppnisnúmer $l$ ($0 \le l \le L - 1$) er punktur $l$.
• Eftir að maraþonhlaupið hefst hreyfast þátttakendurnir í $T$ sekúndur réttsælis í kringum vatnið, hver á sínum hraða. Augnablikið þegar $t$ sekúndur ($0 \le t \le T$) eru liðnar frá upphafi maraþonhlaupsins kallast tími $t$.

Bitaro er með þátttakendalista maraþonhlaupsins. Eins og er eru $N$ þátttakendur skráðir á þátttakendalistann, og $i$-ti þátttakandinn ($1 \le i \le N$) á að bera keppnisnúmer $A_i$ og hreyfast réttsælis í kringum vatnið á hraðanum $S_i$ á hverri $1$ sekúndu.

Út frá þátttakendalistanum fann Bitaro fjölda árekstra sem verða í maraþonhlaupinu. Hér vísar árekstur til þess að $2$ ólíkir þátttakendur séu á sama stað. Nákvæmar tiltekið fann hann fjölda þrennda $(p, q, t)$ sem samanstanda af heiltölum $p, q$ sem uppfylla $0 \le p < q \le L - 1$ og rauntölu $t$ sem uppfyllir $0 \le t \le T$ og uppfylla eftirfarandi skilyrði:

• Það er þátttakandi sem ber keppnisnúmer $p$.
• Það er þátttakandi sem ber keppnisnúmer $q$.
• Þátttakandinn sem ber keppnisnúmer $p$ og þátttakandinn sem ber keppnisnúmer $q$ eru á sama stað á tíma $t$.

Hins vegar voru síðar gerðar $Q$ breytingar á þátttakendalistanum. $j$-ta breytingin ($1 \le j \le Q$) er táknuð með $2$ heiltölum $X_j, Y_j$ og er sem hér segir:

• Ef nú er skráður á þátttakendalistann einstaklingur sem ber keppnisnúmer $X_j$ og hreyfist réttsælis í kringum vatnið á hraðanum $Y_j$ á hverri $1$ sekúndu, þá er sá einstaklingur fjarlægður af þátttakendalistanum. Annars er nýjum einstaklingi sem ber keppnisnúmer $X_j$ og hreyfist réttsælis í kringum vatnið á hraðanum $Y_j$ á hverri $1$ sekúndu bætt við þátttakendalistann.

Þó er tryggt að þegar hvaða breytingu sem er lýkur eru $2$ eða fleiri þátttakendur skráðir á þátttakendalistann, og keppnisnúmerin sem þátttakendurnir bera eru öll innbyrðis ólík.

Bitaro vill vita, fyrir þátttakendurna þegar hverri breytingu lýkur, fjölda árekstra sem verða í maraþonhlaupinu. Út frá skorðum verkefnisins má sanna að fjöldi árekstra sem verða í maraþonhlaupinu er endanlegur.

Gefnar upplýsingar um maraþonhlaupið og breytingarnar á þátttakendalistanum, skrifaðu forrit til að finna, fyrir þátttakendurna þegar hverri breytingu lýkur, afganginn þegar fjöldi árekstra sem verða í maraþonhlaupinu er deilt með $1000000007$.

Takmarkanir

• $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$).
• Þegar hvaða breytingu sem er lýkur eru $2$ eða fleiri þátttakendur.
• Þegar hvaða breytingu sem er lýkur eru upphafsstaðir þátttakendanna innbyrðis ólíkir.
• Öll inntaksgildi eru heiltölur.

Undirverkefni

1. ($10$ stig) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ stig) $N \le 2000$, $Q = 1$.
3. ($11$ stig) $N \le 2000$, $Q \le 2000$.
4. ($27$ stig) $Q = 1$.
5. ($34$ stig) $N + Q \le 78000$.
6. ($10$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið á eftirfarandi sniði: $$\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}$$

Úttak

Prentið $Q$ línur. Á $j$-tu línu ($1 \le j \le Q$) skal prenta afganginn þegar fjölda árekstra sem verða í maraþonhlaupinu meðal þátttakendanna þegar $j$-tu breytingunni lýkur er deilt með $1000000007$.

Dæmi

Dæmi 1

Inntak

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

Úttak

7

Útskýring

Það eru $4$ þátttakendur þegar $1$. breytingunni lýkur. Upplýsingarnar um hvern þátttakanda eru sem hér segir:

1. Ber keppnisnúmer $1$ og byrjar í punkti $1$. Hreyfist réttsælis á hraðanum $4$ á hverri $1$ sekúndu.
2. Ber keppnisnúmer $6$ og byrjar í punkti $6$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
3. Ber keppnisnúmer $3$ og byrjar í punkti $3$. Hreyfist réttsælis á hraðanum $6$ á hverri $1$ sekúndu.
4. Ber keppnisnúmer $4$ og byrjar í punkti $4$. Hreyfist réttsælis á hraðanum $2$ á hverri $1$ sekúndu.

Meðal þátttakendanna þegar $1$. breytingunni lýkur verða eftirfarandi $7$ árekstrar í maraþonhlaupinu:

1. Á tíma $1 \div 4$ eru þátttakandinn með keppnisnúmer $3$ og þátttakandinn með keppnisnúmer $4$ á sama stað $9 \div 2$.
2. Á tíma $3 \div 5$ eru þátttakandinn með keppnisnúmer $3$ og þátttakandinn með keppnisnúmer $6$ á sama stað $33 \div 5$.
3. Á tíma $3 \div 2$ eru þátttakandinn með keppnisnúmer $1$ og þátttakandinn með keppnisnúmer $4$ á sama stað $0$.
4. Á tíma $5 \div 3$ eru þátttakandinn með keppnisnúmer $1$ og þátttakandinn með keppnisnúmer $6$ á sama stað $2 \div 3$.
5. Á tíma $2$ eru þátttakandinn með keppnisnúmer $3$ og þátttakandinn með keppnisnúmer $4$ á sama stað $1$.
6. Á tíma $2$ eru þátttakandinn með keppnisnúmer $3$ og þátttakandinn með keppnisnúmer $6$ á sama stað $1$.
7. Á tíma $2$ eru þátttakandinn með keppnisnúmer $4$ og þátttakandinn með keppnisnúmer $6$ á sama stað $1$.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 4, 5, 6$.

Dæmi 2

Inntak

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

Úttak

1
0

Útskýring

Það eru $4$ þátttakendur þegar $1$. breytingunni lýkur. Upplýsingarnar um hvern þátttakanda eru sem hér segir:

1. Ber keppnisnúmer $1$ og byrjar í punkti $1$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
2. Ber keppnisnúmer $3$ og byrjar í punkti $3$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
3. Ber keppnisnúmer $4$ og byrjar í punkti $4$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
4. Ber keppnisnúmer $0$ og byrjar í punkti $0$. Hreyfist réttsælis á hraðanum $2$ á hverri $1$ sekúndu.

Meðal þátttakendanna þegar $1$. breytingunni lýkur verður eftirfarandi $1$ árekstur í maraþonhlaupinu:

1. Á tíma $1$ eru þátttakandinn með keppnisnúmer $0$ og þátttakandinn með keppnisnúmer $1$ á sama stað $2$.

Það eru $3$ þátttakendur þegar $2$. breytingunni lýkur. Upplýsingarnar um hvern þátttakanda eru sem hér segir:

1. Ber keppnisnúmer $3$ og byrjar í punkti $3$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
2. Ber keppnisnúmer $4$ og byrjar í punkti $4$. Hreyfist réttsælis á hraðanum $1$ á hverri $1$ sekúndu.
3. Ber keppnisnúmer $0$ og byrjar í punkti $0$. Hreyfist réttsælis á hraðanum $2$ á hverri $1$ sekúndu.

Meðal þátttakendanna þegar $2$. breytingunni lýkur verða $0$ árekstrar í maraþonhlaupinu.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 3, 5, 6$.

Dæmi 3

Inntak

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Úttak

9265409

Útskýring

Það eru $3$ þátttakendur þegar $1$. breytingunni lýkur. Upplýsingarnar um hvern þátttakanda eru sem hér segir:

1. Ber keppnisnúmer $58683$ og byrjar í punkti $58683$. Hreyfist réttsælis á hraðanum $28489$ á hverri $1$ sekúndu.
2. Ber keppnisnúmer $3478$ og byrjar í punkti $3478$. Hreyfist réttsælis á hraðanum $48682814$ á hverri $1$ sekúndu.
3. Ber keppnisnúmer $28482$ og byrjar í punkti $28482$. Hreyfist réttsælis á hraðanum $39599461$ á hverri $1$ sekúndu.

Meðal þátttakendanna þegar $1$. breytingunni lýkur verða $967009272178$ árekstrar í maraþonhlaupinu. Því er afgangurinn þegar fjölda árekstra sem verða í maraþonhlaupinu er deilt með $1000000007$ jafn $9265409$.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 4, 5, 6$.

Dæmi 4

Inntak

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

Úttak

330
264
341
440
341

Útskýring

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $3, 5, 6$.