Treść zadania

Bitaro mieszka wokół dużego okrągłego jeziora. Obwód jeziora wynosi $L$, a w pewnym punkcie nad brzegiem jeziora znajduje się dom Bitaro. Punkt, do którego dociera się po przebyciu odległości $x$ ($0 \le x < L$) zgodnie z ruchem wskazówek zegara wzdłuż brzegu jeziora, licząc od domu Bitaro, nazywamy punktem $x$. Obecnie planowany jest maraton wokół jeziora.

Bitaro usłyszał, że maraton ma przebiegać w następujący sposób:

• Przygotowano numery startowe ponumerowane od $0$ do $L - 1$, po $1$ egzemplarzu każdego. Każdy uczestnik maratonu nosi jeden z numerów startowych. Punktem startowym uczestnika noszącego numer startowy $l$ ($0 \le l \le L - 1$) jest punkt $l$.
• Po rozpoczęciu maratonu przez $T$ sekund uczestnicy poruszają się wokół jeziora zgodnie z ruchem wskazówek zegara ze swoimi prędkościami. Moment, w którym od startu maratonu upłynęło $t$ sekund ($0 \le t \le T$), nazywamy chwilą $t$.

Bitaro ma listę uczestników maratonu. Obecnie na liście uczestników zapisanych jest $N$ uczestników, a $i$-ty uczestnik ($1 \le i \le N$) ma nosić numer startowy $A_i$ i poruszać się wokół jeziora zgodnie z ruchem wskazówek zegara z prędkością $S_i$ na $1$ sekundę.

Na podstawie listy uczestników Bitaro wyznaczył liczbę kolizji, które następują podczas maratonu. Tutaj kolizja oznacza sytuację, w której $2$ różnych uczestników znajduje się w tym samym punkcie. Ściśle mówiąc, wyznaczył on liczbę trójek $(p, q, t)$ złożonych z liczb całkowitych $p, q$ spełniających $0 \le p < q \le L - 1$ oraz liczby rzeczywistej $t$ spełniającej $0 \le t \le T$, które spełniają następujące warunki:

• Istnieje uczestnik noszący numer startowy $p$.
• Istnieje uczestnik noszący numer startowy $q$.
• Uczestnik noszący numer startowy $p$ oraz uczestnik noszący numer startowy $q$ znajdują się w tym samym punkcie w chwili $t$.

Jednak później na liście uczestników dokonano $Q$ zmian. $j$-ta zmiana ($1 \le j \le Q$) jest reprezentowana przez $2$ liczby całkowite $X_j, Y_j$ i wygląda następująco:

• Jeśli obecnie na liście uczestników figuruje osoba, która nosi numer startowy $X_j$ i porusza się wokół jeziora zgodnie z ruchem wskazówek zegara z prędkością $Y_j$ na $1$ sekundę, usuwamy tę osobę z listy uczestników. W przeciwnym razie dopisujemy do listy uczestników nową osobę, która nosi numer startowy $X_j$ i porusza się wokół jeziora zgodnie z ruchem wskazówek zegara z prędkością $Y_j$ na $1$ sekundę.

Gwarantowane jest przy tym, że po zakończeniu dowolnej zmiany na liście uczestników zapisanych jest co najmniej $2$ uczestników, a numery startowe noszone przez uczestników są parami różne.

Bitaro chciałby wiedzieć, dla uczestników z momentu zakończenia każdej zmiany, ile kolizji następuje podczas maratonu. Z ograniczeń podanych w treści zadania można udowodnić, że liczba kolizji następujących podczas maratonu jest skończona.

Mając dane informacje o maratonie oraz zmianach na liście uczestników, napisz program, który dla uczestników z momentu zakończenia każdej zmiany wyznaczy resztę z dzielenia liczby kolizji następujących podczas maratonu przez $1000000007$.

Ograniczenia

• $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$).
• Po zakończeniu dowolnej zmiany jest co najmniej $2$ uczestników.
• Po zakończeniu dowolnej zmiany punkty startowe uczestników są parami różne.
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Podzadania

1. ($10$ punktów) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$).
2. ($8$ punktów) $N \le 2000$, $Q = 1$.
3. ($11$ punktów) $N \le 2000$, $Q \le 2000$.
4. ($27$ punktów) $Q = 1$.
5. ($34$ punktów) $N + Q \le 78000$.
6. ($10$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podawane jest w następującym formacie: $$\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}$$

Wyjście

Wypisz $Q$ wierszy. W $j$-tym wierszu ($1 \le j \le Q$) wypisz resztę z dzielenia przez $1000000007$ liczby kolizji następujących podczas maratonu wśród uczestników z momentu zakończenia $j$-tej zmiany.

Przykład

Przykład 1

Wejście

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

Wyjście

7

Wyjaśnienie

W momencie zakończenia $1$-szej zmiany jest $4$ uczestników. Informacje o poszczególnych uczestnikach są następujące:

1. Nosi numer startowy $1$ i startuje z punktu $1$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $4$ na $1$ sekundę.
2. Nosi numer startowy $6$ i startuje z punktu $6$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
3. Nosi numer startowy $3$ i startuje z punktu $3$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $6$ na $1$ sekundę.
4. Nosi numer startowy $4$ i startuje z punktu $4$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $2$ na $1$ sekundę.

Wśród uczestników z momentu zakończenia $1$-szej zmiany podczas maratonu dochodzi do następujących $7$ kolizji:

1. W chwili $1 \div 4$ uczestnik z numerem startowym $3$ i uczestnik z numerem startowym $4$ znajdują się w tym samym punkcie $9 \div 2$.
2. W chwili $3 \div 5$ uczestnik z numerem startowym $3$ i uczestnik z numerem startowym $6$ znajdują się w tym samym punkcie $33 \div 5$.
3. W chwili $3 \div 2$ uczestnik z numerem startowym $1$ i uczestnik z numerem startowym $4$ znajdują się w tym samym punkcie $0$.
4. W chwili $5 \div 3$ uczestnik z numerem startowym $1$ i uczestnik z numerem startowym $6$ znajdują się w tym samym punkcie $2 \div 3$.
5. W chwili $2$ uczestnik z numerem startowym $3$ i uczestnik z numerem startowym $4$ znajdują się w tym samym punkcie $1$.
6. W chwili $2$ uczestnik z numerem startowym $3$ i uczestnik z numerem startowym $6$ znajdują się w tym samym punkcie $1$.
7. W chwili $2$ uczestnik z numerem startowym $4$ i uczestnik z numerem startowym $6$ znajdują się w tym samym punkcie $1$.

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

Przykład 2

Wejście

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

Wyjście

1
0

Wyjaśnienie

W momencie zakończenia $1$-szej zmiany jest $4$ uczestników. Informacje o poszczególnych uczestnikach są następujące:

1. Nosi numer startowy $1$ i startuje z punktu $1$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
2. Nosi numer startowy $3$ i startuje z punktu $3$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
3. Nosi numer startowy $4$ i startuje z punktu $4$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
4. Nosi numer startowy $0$ i startuje z punktu $0$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $2$ na $1$ sekundę.

Wśród uczestników z momentu zakończenia $1$-szej zmiany podczas maratonu dochodzi do następującej $1$ kolizji:

1. W chwili $1$ uczestnik z numerem startowym $0$ i uczestnik z numerem startowym $1$ znajdują się w tym samym punkcie $2$.

W momencie zakończenia $2$-giej zmiany jest $3$ uczestników. Informacje o poszczególnych uczestnikach są następujące:

1. Nosi numer startowy $3$ i startuje z punktu $3$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
2. Nosi numer startowy $4$ i startuje z punktu $4$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $1$ na $1$ sekundę.
3. Nosi numer startowy $0$ i startuje z punktu $0$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $2$ na $1$ sekundę.

Wśród uczestników z momentu zakończenia $2$-giej zmiany podczas maratonu dochodzi do $0$ kolizji.

Ten przykład wejściowy spełnia ograniczenia podzadań $1, 3, 5, 6$.

Przykład 3

Wejście

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

Wyjście

9265409

Wyjaśnienie

W momencie zakończenia $1$-szej zmiany jest $3$ uczestników. Informacje o poszczególnych uczestnikach są następujące:

1. Nosi numer startowy $58683$ i startuje z punktu $58683$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $28489$ na $1$ sekundę.
2. Nosi numer startowy $3478$ i startuje z punktu $3478$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $48682814$ na $1$ sekundę.
3. Nosi numer startowy $28482$ i startuje z punktu $28482$. Porusza się zgodnie z ruchem wskazówek zegara z prędkością $39599461$ na $1$ sekundę.

Wśród uczestników z momentu zakończenia $1$-szej zmiany podczas maratonu dochodzi do $967009272178$ kolizji. Zatem reszta z dzielenia liczby kolizji podczas maratonu przez $1000000007$ wynosi $9265409$.

Ten przykład wejściowy spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

Przykład 4

Wejście

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

Wyjście

330
264
341
440
341

Wyjaśnienie

Ten przykład wejściowy spełnia ograniczenia podzadań $3, 5, 6$.