충돌

문제

비타로는 커다란 원형 호수의 주위에 살고 있다. 호수의 둘레 길이는 $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$ 명 이상이며, 참가자가 착용하는 번호표는 서로 다름이 보장된다.

비타로는 각각의 변경이 끝난 시점의 참가자에 대하여, 마라톤 대회 중에 일어나는 충돌의 횟수를 알고 싶다. 문제의 제약에 의해, 마라톤 대회 중에 일어나는 충돌의 횟수가 유한함을 증명할 수 있다.

마라톤 대회와 참가자 명부에 대한 변경의 정보가 주어졌을 때, 각각의 변경이 끝난 시점의 참가자에 대하여 마라톤 대회 중에 일어나는 충돌의 횟수를 $1\,000\,000\,007$ 로 나눈 나머지를 구하는 프로그램을 작성하시오.

제한

• $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} \neq 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 100\,000$.
• $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 2\,000$, $Q = 1$.
3. ($11$ 점) $N \le 2\,000$, $Q \le 2\,000$.
4. ($27$ 점) $Q = 1$.
5. ($34$ 점) $N + Q \le 78\,000$.
6. ($10$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$ $L$ $T$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$S_{1}$ $S_{2}$ $\dots$ $S_{N}$
$Q$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$:$
$X_{Q}$ $Y_{Q}$

출력

$Q$ 개의 줄에 출력한다. $j$ 번째 줄 ($1 \le j \le Q$) 에는 $j$ 번째 변경이 끝난 시점의 참가자에 대하여, 마라톤 대회 중에 일어나는 충돌의 횟수를 $1\,000\,000\,007$ 로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

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

예제 출력 2

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

예제 출력 3

9265409

$1$ 번째 변경이 끝난 시점의 참가자는 $3$ 명이다. 각각의 참가자에 대한 정보는 다음과 같다.

1. 번호표 $58\,683$ 을 착용하고, 지점 $58\,683$ 에서 출발한다. $1$ 초당 $28\,489$ 의 속도로 시계 방향으로 이동한다.
2. 번호표 $3\,478$ 을 착용하고, 지점 $3\,478$ 에서 출발한다. $1$ 초당 $48\,682\,814$ 의 속도로 시계 방향으로 이동한다.
3. 번호표 $28\,482$ 를 착용하고, 지점 $28\,482$ 에서 출발한다. $1$ 초당 $39\,599\,461$ 의 속도로 시계 방향으로 이동한다.

$1$ 번째 변경이 끝난 시점의 참가자에 대하여, 마라톤 대회 중의 충돌은 $967\,009\,272\,178$ 번이 된다. 따라서 마라톤 대회 중에 일어나는 충돌의 횟수를 $1\,000\,000\,007$ 로 나눈 나머지는 $9\,265\,409$ 가 된다.

이 예제는 서브태스크 $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

예제 출력 4

330
264
341
440
341

이 예제는 서브태스크 $3,5,6$ 의 제약을 만족한다.