Есептің шарты

Битаро үлкен дөңгелек көлдің айналасында тұрады. Көл жиегінің ұзындығы $L$, ал көл жиегіндегі белгілі бір нүктеде Битароның үйі орналасқан. Битароның үйінен көл жиегімен сағат тілі бағытымен $x$ ($0 \le x < L$) қашықтыққа жылжығанда жететін нүктені $x$ нүктесі деп атаймыз. Қазіргі уақытта көлді айналып өтетін марафон жарысы жоспарлануда.

Битаро марафон жарысы келесідей өтетінін естіді:

• $0$-ден $L - 1$-ге дейін нөмірленген кеудеше нөмірлерінің әрқайсысынан $1$ данадан дайындалған. Марафон жарысына қатысушылардың әрқайсысы осы нөмірлердің бірін тағады. $l$ ($0 \le l \le L - 1$) нөмірін таққан қатысушының бастапқы нүктесі $l$ нүктесі болады.
• Марафон жарысы басталғаннан кейін $T$ секунд бойы қатысушылар өз жылдамдықтарымен көлді айналып сағат тілі бағытымен қозғалады. Марафон жарысы басталғаннан бері $t$ секунд ($0 \le t \le T$) өткен мезет $t$ уақыт мезеті деп аталады.

Битарода марафон жарысына қатысушылардың тізімі бар. Қазіргі уақытта қатысушылар тізімінде $N$ қатысушы тіркелген, ал $i$-ші қатысушы ($1 \le i \le N$) $A_i$ нөмірін тағып, $1$ секундта $S_i$ жылдамдықпен көлді айналып сағат тілі бағытымен қозғалуды жоспарлап отыр.

Қатысушылар тізіміне сүйене отырып, Битаро марафон жарысы кезінде орын алатын соқтығысулар санын тапты. Мұнда соқтығысу дегеніміз әртүрлі $2$ қатысушының бір нүктеде болуын білдіреді. Дәлірек айтқанда, ол $0 \le p < q \le L - 1$ шартын қанағаттандыратын $p, q$ бүтін сандарынан және $0 \le t \le T$ шартын қанағаттандыратын $t$ нақты санынан тұратын, келесі шарттарды қанағаттандыратын $(p, q, t)$ үштіктерінің санын тапты:

• $p$ нөмірін таққан қатысушы бар.
• $q$ нөмірін таққан қатысушы бар.
• $p$ нөмірін таққан қатысушы мен $q$ нөмірін таққан қатысушы $t$ уақыт мезетінде бір нүктеде болады.

Алайда содан кейін қатысушылар тізіміне $Q$ рет өзгеріс енгізілді. $j$-ші өзгеріс ($1 \le j \le Q$) $2$ бүтін санмен $X_j, Y_j$ сипатталады және келесідей орындалады:

• Қазіргі уақытта қатысушылар тізімінде $X_j$ нөмірін тағып, $1$ секундта $Y_j$ жылдамдықпен көлді айналып сағат тілі бағытымен қозғалатын адам бар болса, ол адамды қатысушылар тізімінен өшіреді. Олай болмаса, қатысушылар тізіміне $X_j$ нөмірін тағып, $1$ секундта $Y_j$ жылдамдықпен көлді айналып сағат тілі бағытымен қозғалатын жаңа адамды қосады.

Дегенмен, кез келген өзгеріс аяқталған мезетте қатысушылар тізімінде кемінде $2$ қатысушы бар екеніне және қатысушылар таққан нөмірлердің өзара әртүрлі екеніне кепілдік беріледі.

Битаро әрбір өзгеріс аяқталған мезеттегі қатысушылар үшін марафон жарысы кезінде орын алатын соқтығысулар санын білгісі келеді. Есептің шектеулерінен марафон жарысы кезінде орын алатын соқтығысулар санының шекті екенін дәлелдеуге болады.

Марафон жарысы және қатысушылар тізіміндегі өзгерістер туралы ақпарат берілген кезде, әрбір өзгеріс аяқталған мезеттегі қатысушылар үшін марафон жарысы кезінде орын алатын соқтығысулар санын $1000000007$-ге бөлгендегі қалдықты табатын программа жазыңыз.

Шектеулер

• $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$).
• Кез келген өзгеріс аяқталған мезетте кемінде $2$ қатысушы бар.
• Кез келген өзгеріс аяқталған мезетте қатысушылардың бастапқы нүктелері өзара әртүрлі.
• Барлық кіріс мәндері — бүтін сандар.

Ішкі есептер

1. ($10$ ұпай) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ ұпай) $N \le 2000$, $Q = 1$.
3. ($11$ ұпай) $N \le 2000$, $Q \le 2000$.
4. ($27$ ұпай) $Q = 1$.
5. ($34$ ұпай) $N + Q \le 78000$.
6. ($10$ ұпай) Қосымша шектеулер жоқ.

Кіріс деректер

Кіріс деректер келесі форматта беріледі: $$\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}$$

Шығыс деректер

$Q$ жол шығарыңыз. $j$-ші жолда ($1 \le j \le Q$) $j$-ші өзгеріс аяқталған мезеттегі қатысушылар арасында марафон жарысы кезінде орын алатын соқтығысулар санын $1000000007$-ге бөлгендегі қалдықты шығарыңыз.

Мысал

Мысал 1

Кіріс деректер

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

Шығыс деректер

7

Түсіндірме

$1$-ші өзгеріс аяқталған мезетте $4$ қатысушы бар. Әрбір қатысушы туралы ақпарат келесідей:

1. $1$ нөмірін тағып, $1$ нүктесінен бастайды. $1$ секундта $4$ жылдамдықпен сағат тілі бағытымен қозғалады.
2. $6$ нөмірін тағып, $6$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
3. $3$ нөмірін тағып, $3$ нүктесінен бастайды. $1$ секундта $6$ жылдамдықпен сағат тілі бағытымен қозғалады.
4. $4$ нөмірін тағып, $4$ нүктесінен бастайды. $1$ секундта $2$ жылдамдықпен сағат тілі бағытымен қозғалады.

$1$-ші өзгеріс аяқталған мезеттегі қатысушылар арасында марафон жарысы кезінде келесі $7$ соқтығысу орын алады:

1. $1 \div 4$ уақыт мезетінде $3$ нөмірін таққан қатысушы мен $4$ нөмірін таққан қатысушы бірдей $9 \div 2$ нүктесінде болады.
2. $3 \div 5$ уақыт мезетінде $3$ нөмірін таққан қатысушы мен $6$ нөмірін таққан қатысушы бірдей $33 \div 5$ нүктесінде болады.
3. $3 \div 2$ уақыт мезетінде $1$ нөмірін таққан қатысушы мен $4$ нөмірін таққан қатысушы бірдей $0$ нүктесінде болады.
4. $5 \div 3$ уақыт мезетінде $1$ нөмірін таққан қатысушы мен $6$ нөмірін таққан қатысушы бірдей $2 \div 3$ нүктесінде болады.
5. $2$ уақыт мезетінде $3$ нөмірін таққан қатысушы мен $4$ нөмірін таққан қатысушы бірдей $1$ нүктесінде болады.
6. $2$ уақыт мезетінде $3$ нөмірін таққан қатысушы мен $6$ нөмірін таққан қатысушы бірдей $1$ нүктесінде болады.
7. $2$ уақыт мезетінде $4$ нөмірін таққан қатысушы мен $6$ нөмірін таққан қатысушы бірдей $1$ нүктесінде болады.

Бұл кіріс мысалы $2, 3, 4, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

Мысал 2

Кіріс деректер

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

Шығыс деректер

1
0

Түсіндірме

$1$-ші өзгеріс аяқталған мезетте $4$ қатысушы бар. Әрбір қатысушы туралы ақпарат келесідей:

1. $1$ нөмірін тағып, $1$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
2. $3$ нөмірін тағып, $3$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
3. $4$ нөмірін тағып, $4$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
4. $0$ нөмірін тағып, $0$ нүктесінен бастайды. $1$ секундта $2$ жылдамдықпен сағат тілі бағытымен қозғалады.

$1$-ші өзгеріс аяқталған мезеттегі қатысушылар арасында марафон жарысы кезінде келесі $1$ соқтығысу орын алады:

1. $1$ уақыт мезетінде $0$ нөмірін таққан қатысушы мен $1$ нөмірін таққан қатысушы бірдей $2$ нүктесінде болады.

$2$-ші өзгеріс аяқталған мезетте $3$ қатысушы бар. Әрбір қатысушы туралы ақпарат келесідей:

1. $3$ нөмірін тағып, $3$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
2. $4$ нөмірін тағып, $4$ нүктесінен бастайды. $1$ секундта $1$ жылдамдықпен сағат тілі бағытымен қозғалады.
3. $0$ нөмірін тағып, $0$ нүктесінен бастайды. $1$ секундта $2$ жылдамдықпен сағат тілі бағытымен қозғалады.

$2$-ші өзгеріс аяқталған мезеттегі қатысушылар арасында марафон жарысы кезінде $0$ соқтығысу орын алады.

Бұл кіріс мысалы $1, 3, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

Мысал 3

Кіріс деректер

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Шығыс деректер

9265409

Түсіндірме

$1$-ші өзгеріс аяқталған мезетте $3$ қатысушы бар. Әрбір қатысушы туралы ақпарат келесідей:

1. $58683$ нөмірін тағып, $58683$ нүктесінен бастайды. $1$ секундта $28489$ жылдамдықпен сағат тілі бағытымен қозғалады.
2. $3478$ нөмірін тағып, $3478$ нүктесінен бастайды. $1$ секундта $48682814$ жылдамдықпен сағат тілі бағытымен қозғалады.
3. $28482$ нөмірін тағып, $28482$ нүктесінен бастайды. $1$ секундта $39599461$ жылдамдықпен сағат тілі бағытымен қозғалады.

$1$-ші өзгеріс аяқталған мезеттегі қатысушылар арасында марафон жарысы кезінде $967009272178$ соқтығысу орын алады. Сондықтан марафон жарысы кезінде орын алатын соқтығысулар санын $1000000007$-ге бөлгендегі қалдық $9265409$ болады.

Бұл кіріс мысалы $2, 3, 4, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

Мысал 4

Кіріс деректер

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

Шығыс деректер

330
264
341
440
341

Түсіндірме

Бұл кіріс мысалы $3, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.