문제 설명

비타로는 큰 원형 호수 둘레에 살고 있다. 호수 둘레의 길이는 $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$의 제약 조건을 만족한다.