Deskripsi Soal

Bitaro tinggal di sekitar sebuah danau besar berbentuk lingkaran. Keliling danau tersebut adalah $L$, dan di suatu titik di keliling danau terdapat rumah Bitaro. Titik yang dicapai dengan bergerak sejauh $x$ ($0 \le x < L$) searah jarum jam di sepanjang keliling danau dari rumah Bitaro disebut titik $x$. Saat ini, sebuah lomba maraton yang akan diadakan mengelilingi danau sedang direncanakan.

Bitaro mendengar bahwa lomba maraton tersebut dijadwalkan berlangsung sebagai berikut:

• Nomor dada yang diberi nomor dari $0$ hingga $L - 1$ disiapkan, masing-masing $1$ lembar. Setiap peserta lomba maraton mengenakan salah satu nomor dada tersebut. Titik awal dari peserta yang mengenakan nomor dada $l$ ($0 \le l \le L - 1$) adalah titik $l$.
• Setelah lomba maraton dimulai, selama $T$ detik, para peserta bergerak searah jarum jam mengelilingi danau dengan kecepatan masing-masing. Saat ketika $t$ detik ($0 \le t \le T$) telah berlalu sejak lomba maraton dimulai disebut waktu $t$.

Bitaro memiliki daftar peserta lomba maraton. Saat ini, $N$ peserta tercatat di dalam daftar peserta, dan peserta ke-$i$ ($1 \le i \le N$) dijadwalkan mengenakan nomor dada $A_i$ serta bergerak searah jarum jam mengelilingi danau dengan kecepatan $S_i$ per $1$ detik.

Berdasarkan daftar peserta tersebut, Bitaro menghitung banyaknya tabrakan yang terjadi selama lomba maraton. Di sini, tabrakan berarti $2$ peserta yang berbeda berada di titik yang sama. Secara formal, ia mencari banyaknya tripel $(p, q, t)$ yang terdiri dari bilangan bulat $p, q$ yang memenuhi $0 \le p < q \le L - 1$ dan sebuah bilangan riil $t$ yang memenuhi $0 \le t \le T$ yang memenuhi syarat-syarat berikut:

• Terdapat peserta yang mengenakan nomor dada $p$.
• Terdapat peserta yang mengenakan nomor dada $q$.
• Peserta yang mengenakan nomor dada $p$ dan peserta yang mengenakan nomor dada $q$ berada di titik yang sama pada waktu $t$.

Namun, setelah itu, dilakukan $Q$ perubahan pada daftar peserta. Perubahan ke-$j$ ($1 \le j \le Q$) dinyatakan dengan $2$ bilangan bulat $X_j, Y_j$, dan adalah sebagai berikut:

• Saat ini, jika seseorang yang mengenakan nomor dada $X_j$ dan bergerak searah jarum jam mengelilingi danau dengan kecepatan $Y_j$ per $1$ detik tercatat di dalam daftar peserta, hapus orang tersebut dari daftar peserta. Jika tidak, tambahkan secara baru seseorang yang mengenakan nomor dada $X_j$ dan bergerak searah jarum jam mengelilingi danau dengan kecepatan $Y_j$ per $1$ detik ke dalam daftar peserta.

Akan tetapi, dijamin bahwa pada saat perubahan mana pun selesai, terdapat $2$ atau lebih peserta yang tercatat di dalam daftar peserta, dan nomor dada yang dikenakan oleh para peserta semuanya berbeda.

Bitaro ingin mengetahui, untuk para peserta pada saat setiap perubahan selesai, banyaknya tabrakan yang terjadi selama lomba maraton. Dari batasan soal, dapat dibuktikan bahwa banyaknya tabrakan yang terjadi selama lomba maraton adalah berhingga.

Diberikan informasi mengenai lomba maraton dan perubahan pada daftar peserta, buatlah program untuk mencari sisa pembagian banyaknya tabrakan yang terjadi selama lomba maraton di antara para peserta pada saat setiap perubahan selesai dengan $1000000007$.

Batasan

• $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$).
• Pada saat perubahan mana pun selesai, terdapat $2$ atau lebih peserta.
• Pada saat perubahan mana pun selesai, titik awal para peserta saling berbeda.
• Semua nilai masukan adalah bilangan bulat.

Subsoal

1. ($10$ poin) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ poin) $N \le 2000$, $Q = 1$.
3. ($11$ poin) $N \le 2000$, $Q \le 2000$.
4. ($27$ poin) $Q = 1$.
5. ($34$ poin) $N + Q \le 78000$.
6. ($10$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dalam format berikut: $$\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}$$

Keluaran

Keluarkan $Q$ baris. Pada baris ke-$j$ ($1 \le j \le Q$), keluarkan sisa pembagian banyaknya tabrakan yang terjadi selama lomba maraton pada para peserta saat perubahan ke-$j$ selesai dengan $1000000007$.

Contoh

Contoh 1

Masukan

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

Keluaran

7

Penjelasan

Terdapat $4$ peserta pada saat perubahan ke-$1$ selesai. Informasi mengenai masing-masing peserta adalah sebagai berikut:

1. Mengenakan nomor dada $1$ dan mulai dari titik $1$. Bergerak searah jarum jam dengan kecepatan $4$ per $1$ detik.
2. Mengenakan nomor dada $6$ dan mulai dari titik $6$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
3. Mengenakan nomor dada $3$ dan mulai dari titik $3$. Bergerak searah jarum jam dengan kecepatan $6$ per $1$ detik.
4. Mengenakan nomor dada $4$ dan mulai dari titik $4$. Bergerak searah jarum jam dengan kecepatan $2$ per $1$ detik.

Pada para peserta saat perubahan ke-$1$ selesai, terjadi $7$ tabrakan berikut selama lomba maraton:

1. Pada waktu $1 \div 4$, peserta yang mengenakan nomor dada $3$ dan peserta yang mengenakan nomor dada $4$ berada di titik yang sama yaitu titik $9 \div 2$.
2. Pada waktu $3 \div 5$, peserta yang mengenakan nomor dada $3$ dan peserta yang mengenakan nomor dada $6$ berada di titik yang sama yaitu titik $33 \div 5$.
3. Pada waktu $3 \div 2$, peserta yang mengenakan nomor dada $1$ dan peserta yang mengenakan nomor dada $4$ berada di titik yang sama yaitu titik $0$.
4. Pada waktu $5 \div 3$, peserta yang mengenakan nomor dada $1$ dan peserta yang mengenakan nomor dada $6$ berada di titik yang sama yaitu titik $2 \div 3$.
5. Pada waktu $2$, peserta yang mengenakan nomor dada $3$ dan peserta yang mengenakan nomor dada $4$ berada di titik yang sama yaitu titik $1$.
6. Pada waktu $2$, peserta yang mengenakan nomor dada $3$ dan peserta yang mengenakan nomor dada $6$ berada di titik yang sama yaitu titik $1$.
7. Pada waktu $2$, peserta yang mengenakan nomor dada $4$ dan peserta yang mengenakan nomor dada $6$ berada di titik yang sama yaitu titik $1$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

Contoh 2

Masukan

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

Keluaran

1
0

Penjelasan

Terdapat $4$ peserta pada saat perubahan ke-$1$ selesai. Informasi mengenai masing-masing peserta adalah sebagai berikut:

1. Mengenakan nomor dada $1$ dan mulai dari titik $1$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
2. Mengenakan nomor dada $3$ dan mulai dari titik $3$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
3. Mengenakan nomor dada $4$ dan mulai dari titik $4$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
4. Mengenakan nomor dada $0$ dan mulai dari titik $0$. Bergerak searah jarum jam dengan kecepatan $2$ per $1$ detik.

Pada para peserta saat perubahan ke-$1$ selesai, terjadi $1$ tabrakan berikut selama lomba maraton:

1. Pada waktu $1$, peserta yang mengenakan nomor dada $0$ dan peserta yang mengenakan nomor dada $1$ berada di titik yang sama yaitu titik $2$.

Terdapat $3$ peserta pada saat perubahan ke-$2$ selesai. Informasi mengenai masing-masing peserta adalah sebagai berikut:

1. Mengenakan nomor dada $3$ dan mulai dari titik $3$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
2. Mengenakan nomor dada $4$ dan mulai dari titik $4$. Bergerak searah jarum jam dengan kecepatan $1$ per $1$ detik.
3. Mengenakan nomor dada $0$ dan mulai dari titik $0$. Bergerak searah jarum jam dengan kecepatan $2$ per $1$ detik.

Pada para peserta saat perubahan ke-$2$ selesai, terjadi $0$ tabrakan selama lomba maraton.

Contoh masukan ini memenuhi batasan Subsoal $1, 3, 5, 6$.

Contoh 3

Masukan

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Keluaran

9265409

Penjelasan

Terdapat $3$ peserta pada saat perubahan ke-$1$ selesai. Informasi mengenai masing-masing peserta adalah sebagai berikut:

1. Mengenakan nomor dada $58683$ dan mulai dari titik $58683$. Bergerak searah jarum jam dengan kecepatan $28489$ per $1$ detik.
2. Mengenakan nomor dada $3478$ dan mulai dari titik $3478$. Bergerak searah jarum jam dengan kecepatan $48682814$ per $1$ detik.
3. Mengenakan nomor dada $28482$ dan mulai dari titik $28482$. Bergerak searah jarum jam dengan kecepatan $39599461$ per $1$ detik.

Pada para peserta saat perubahan ke-$1$ selesai, terjadi $967009272178$ tabrakan selama lomba maraton. Oleh karena itu, sisa pembagian banyaknya tabrakan yang terjadi selama lomba maraton dengan $1000000007$ adalah $9265409$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

Contoh 4

Masukan

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

Keluaran

330
264
341
440
341

Penjelasan

Contoh masukan ini memenuhi batasan Subsoal $3, 5, 6$.