충돌

시간 제한9초메모리 제한2048 MB

요약

원형 호수 둘레 L을 달리는 참가자 명단이 주어질 때, 각 추가 또는 삭제 후 T초 동안 두 참가자가 만나는 횟수를 구합니다.

난이도: 어려움10점 중 9점
유형: 수학, 정수론, 정렬
정답자: 아직 제출이 없습니다

문제

비타로는 크고 둥근 호수 둘레에 살고 있다. 호수 둘레의 길이는 $L$ 이고, 둘레의 한 지점에 비타로의 집이 있다. 집에서 호수 둘레를 시계 방향으로 $x$ ( $0 \leq x < L$ )만큼 이동한 지점을 지점 $x$ 라고 부른다. 현재 호수 둘레에서 마라톤 대회가 계획되고 있다.

비타로가 들은 대회 진행 방식은 다음과 같다.

번호 $0$ 부터 $L - 1$ 까지가 적힌 배번이 각각 한 장씩 준비되어 있다. 참가자는 배번 중 하나를 달고 뛴다. 배번 $l$ ( $0 \leq l \leq L - 1$ )을 단 참가자의 출발 지점은 지점 $l$ 이다.
대회가 시작된 뒤 $T$ 초 동안 참가자들은 각자의 속도로 호수 둘레를 시계 방향으로 이동한다. 시작한 지 $t$ 초 ( $0 \leq t \leq T$ )가 지난 시점을 시각 $t$ 라고 부른다.

비타로는 마라톤 대회 참가자 명단을 갖고 있다. 현재 명단에는 $N$ 명이 올라 있다. $i$ 번째 참가자 ( $1 \leq i \leq N$ )는 배번 $A_i$ 를 달고, 초당 $S_i$ 의 속도로 호수 둘레를 시계 방향으로 이동할 예정이다.

명단을 바탕으로 비타로는 대회 중 일어나는 충돌의 횟수를 구했다. 여기서 충돌은 서로 다른 참가자 두 명이 같은 지점에 있는 경우를 말한다. 정확히는, $0 \leq p < q \leq L - 1$ 을 만족하는 정수 $p, q$ 와 $0 \leq t \leq T$ 를 만족하는 실수 $t$ 로 이루어진 순서쌍 $(p, q, t)$ 가운데 다음 조건을 모두 만족하는 것의 개수를 구했다.

배번 $p$ 를 단 참가자가 있다.
배번 $q$ 를 단 참가자가 있다.
배번 $p$ 를 단 참가자와 배번 $q$ 를 단 참가자가 시각 $t$ 에 같은 지점에 있다.

그 뒤 참가자 명단에 $Q$ 번의 변경이 있었다. $j$ 번째 변경 ( $1 \leq j \leq Q$ )은 정수 $X_j$ , $Y_j$ 로 주어지며 다음과 같다.

현재 배번 $X_j$ 를 달고 초당 $Y_j$ 의 속도로 호수 둘레를 시계 방향으로 이동하는 사람이 명단에 있으면, 그 사람을 명단에서 지운다. 없으면, 배번 $X_j$ 를 달고 초당 $Y_j$ 의 속도로 이동하는 사람을 명단에 새로 추가한다.

단, 어떤 변경이 끝난 시점에서도 명단에는 참가자가 2명 이상 있고, 참가자가 단 배번은 모두 서로 다르다고 보장된다.

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

입력

첫 번째 줄에 $N$ , $L$ , $T$ 가 주어진다.

두 번째 줄에 $A_1, A_2, \ldots, A_N$ 이 주어진다.

세 번째 줄에 $S_1, S_2, \ldots, S_N$ 이 주어진다.

네 번째 줄에 $Q$ 가 주어진다.

이어서 $Q$ 개의 줄에 각각 $X_j$ 와 $Y_j$ 가 주어진다.

출력

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

제한

$2 \leq N$ .
$N \leq L \leq 10^9$ .
$1 \leq T \leq 10^9$ .
$0 \leq A_i \leq L - 1$ ( $1 \leq i \leq N$ ).
$A_i \neq A_j$ ( $1 \leq i < j \leq N$ ).
$1 \leq S_i \leq 10^9$ ( $1 \leq i \leq N$ ).
$1 \leq Q$ .
$N + Q \leq 100000$ .
$0 \leq X_j \leq L - 1$ ( $1 \leq j \leq Q$ ).
$1 \leq Y_j \leq 10^9$ ( $1 \leq j \leq Q$ ).
어떤 변경이 끝난 시점에서도 참가자는 2명 이상이다.
어떤 변경이 끝난 시점에서도 참가자의 출발 지점은 서로 다르다.
입력되는 값은 모두 정수이다.

예제4

예제 1
입력
```
3 7 2
1 6 3
4 1 6
1
4 2
```
예상 출력
```
7
```
예제 2
입력
```
3 6 1
1 3 4
1 1 1
2
0 2
1 1
```
예상 출력
```
1
0
```

예제 3

입력

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

예상 출력

예제 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

예상 출력