페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8232
서브태스크

충돌 9초 2048MB

문제

비타로는 큰 원형 호수 주변에 살고 있습니다. 호수의 둘레 길이는 L이고, 호수의 주변에 있는 특정 지점에는 비타로의 집이 있습니다. 비타로의 집에서 호수 주변을 시계방향으로 x (0 ≦ x < L) 만큼 이동한 지점을 지점 x라고 합니다. 현재, 호수 주변에서 마라톤 대회가 예정되어 있습니다.

비타로는 마라톤 대회가 다음과 같이 진행될 것이라고 들었습니다.

0부터 L-1까지 번호가 붙은 번호표가 1장씩 준비되어 있습니다. 마라톤 대회 참가자는 이 번호표 중 하나를 착용합니다. 번호표 l (0 ≦ l ≦ L-1)을 착용한 참가자의 출발 지점은 지점 l이 됩니다. 마라톤 대회가 시작된 후, T초 동안 참가자들은 각자의 속도로 호수 주변을 시계방향으로 이동합니다. 마라톤 대회가 시작된 후, t초 (0 ≦ t ≦ T)가 경과한 시점을 시간 t라고 부릅니다. 비타로는 마라톤 대회 참가자 명단을 가지고 있습니다. 현재 N명의 참가자가 명단에 기록되어 있고, i번째 참가자 (1 ≦ i ≦ N)는 번호표 A_i를 착용하고, 1초에 S_i의 속도로 호수 주변을 시계방향으로 이동할 예정입니다.

참가자 명단을 바탕으로, 비타로는 마라톤 대회 중에 일어나는 충돌 횟수를 구하려고 합니다. 여기서 충돌이란, 서로 다른 2명의 참가자가 같은 지점에 있는 경우를 말합니다. 정확히는, 0 ≦ p < q ≦ L-1을 만족하는 정수 p, q와 0 ≦ t ≦ T을 만족하는 실수 t에서 다음 조건을 만족하는 경우를 충돌로 정의합니다.

  • 번호표 p를 착용한 참가자가 있음.

  • 번호표 q를 착용한 참가자가 있음.

  • 번호표 p를 착용한 참가자와 번호표 q를 착용한 참가자가 시간 t에 같은 지점에 있음.

하지만, 그 후 참가자 명단에 Q번의 변경이 이루어졌습니다. j번째 (1 ≦ j ≦ Q)의 변경은 2개의 정수 X_j, Y_j로 표현되며, 다음과 같은 방식으로 이루어집니다.

현재, 번호표 X_j을 착용하고, 1초에 Y_j의 속도로 호수 주변을 시계방향으로 이동하는 사람이 참가자 명단에 기록되어 있으면, 그 사람을 참가자 명단에서 삭제합니다. 그렇지 않으면, 번호표 X_j을 착용하고, 1초에 Y_j의 속도로 호수 주변을 시계방향으로 이동하는 사람을 새로 참가자 명단에 추가합니다.

단, 변경이 완료된 후에도 참가자 명단에 기록된 참가자는 2명 이상이며, 참가자들이 착용한 번호표는 모두 다를 것이라고 보장됩니다.

비타로는 각각의 변경이 완료된 후, 참가자들에 의해 일어날 충돌의 횟수를 알고 싶습니다. 문제의 제약에 의해, 마라톤 대회 중 발생하는 충돌 횟수는 유한하다는 것이 증명됩니다.

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


입력

입력은 다음과 같은 형식으로 주어진다.

N\ L\ T

A_1\ A_2\ …\ A_N

S_1\ S_2\ …\ S_N

Q

X_1 Y_1

X_2 Y_2

:

X_Q Y_Q

[제약 조건]

  • 2 ≦ N

  • N ≦ L ≦ 10^9

  • 1 ≦ T ≦ 10^9

  • 0 ≦ A_i ≦ L - 1 (1 ≦ i ≦ N)

  • A_i ≠ A_j (1 ≦ i < j ≦ N)

  • 1 ≦ S_i ≦ 10^9 (1 ≦ i ≦ N)

  • 1 ≦ Q

  • N + Q ≦ 100\ 000

  • 0 ≦ X_j ≦ L - 1 (1 ≦ j ≦ Q)

  • 1 ≦ Y_j ≦ 10^9 (1 ≦ j ≦ Q)

  • 각 변경이 끝난 후, 참가자 명단에 기록된 참가자는 2명 이상이어야 합니다.

  • 각 변경이 끝난 후, 참가자들의 출발 지점은 서로 다릅니다.

  • 입력되는 값은 모두 정수입니다.


출력

행에 걸쳐 출력하십시오. j번째 (1 ≦ j ≦ Q) 변경이 끝난 후 참가자들에 의해 일어날 마라톤 대회 중 충돌 횟수를 1,000,000,007로 나눈 나머지를 출력하시오.


부분문제

번호 점수 조건
#110점

T = 1，S_i ≦ 2 (1 ≦ i ≦ N)，Y_j ≦ 2 (1 ≦ j ≦ Q)

#28점

N ≦ 2 000，Q = 1

#311점

N ≦ 2 000，Q ≦ 2 000

#427점

Q = 1

#534점

N + Q ≦ 78 000

#610점

추가 제약 조건 없음


예제1

입력
372
163
416
1
42
출력
7

1번째 변경이 종료된 시점에서 참가자는 4명입니다. 각 참가자에 대한 정보는 다음과 같습니다.

  • 번호표 1을 착용하고, 지점 1에서 출발합니다. 1초당 4의 속도로 시계방향으로 이동합니다.

  • 번호표 6을 착용하고, 지점 6에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 3을 착용하고, 지점 3에서 출발합니다. 1초당 6의 속도로 시계방향으로 이동합니다.

  • 번호표 4를 착용하고, 지점 4에서 출발합니다. 1초당 2의 속도로 시계방향으로 이동합니다.

1번째 변경이 종료된 시점에서 발생한 마라톤 대회 중 충돌은 다음과 같습니다.

  • 시간 1/4에서, 번호표 3을 착용한 참가자와 번호표 4을 착용한 참가자가 같은 지점 9/2에 있습니다.

  • 시간 3/5에서, 번호표 3을 착용한 참가자와 번호표 6을 착용한 참가자가 같은 지점 33/5에 있습니다.

  • 시간 3/2에서, 번호표 1을 착용한 참가자와 번호표 4을 착용한 참가자가 같은 지점 0에 있습니다.

  • 시간 5/3에서, 번호표 1을 착용한 참가자와 번호표 6을 착용한 참가자가 같은 지점 2/3에 있습니다.

  • 시간 2에서, 번호표 3을 착용한 참가자와 번호표 4을 착용한 참가자가 같은 지점 1에 있습니다.

  • 시간 2에서, 번호표 3을 착용한 참가자와 번호표 6을 착용한 참가자가 같은 지점 1에 있습니다.

  • 시간 2에서, 번호표 4를 착용한 참가자와 번호표 6을 착용한 참가자가 같은 지점 1에 있습니다.

이 입력 예시는 서브태스크 2, 3, 4, 5, 6의 제약을 만족합니다.


예제2

입력
361
134
111
2
02
11
출력
1
0

1번째 변경이 종료된 시점에서 참가자는 4명입니다. 각 참가자에 대한 정보는 다음과 같습니다.

  • 번호표 1을 착용하고, 지점 1에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 3을 착용하고, 지점 3에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 4를 착용하고, 지점 4에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 0을 착용하고, 지점 0에서 출발합니다. 1초당 2의 속도로 시계방향으로 이동합니다.

1번째 변경이 종료된 시점에서 발생한 마라톤 대회 중 충돌은 다음과 같습니다.

  • 시간 1에서, 번호표 0을 착용한 참가자와 번호표 1을 착용한 참가자가 같은 지점 2에 있습니다.

2번째 변경이 종료된 시점에서 참가자는 3명입니다. 각 참가자에 대한 정보는 다음과 같습니다.

  • 번호표 3을 착용하고, 지점 3에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 4를 착용하고, 지점 4에서 출발합니다. 1초당 1의 속도로 시계방향으로 이동합니다.

  • 번호표 0을 착용하고, 지점 0에서 출발합니다. 1초당 2의 속도로 시계방향으로 이동합니다.

2번째 변경이 종료된 시점에서 발생한 마라톤 대회 중 충돌은 0번입니다.

이 입력 예시는 서브태스크 1, 3, 5, 6의 제약을 만족합니다.


예제3

입력
2100000993754689
586833478
2848948682814
1
2848239599461
출력
9265409

예제4

입력
7100100
34124623576399
12342312341223
5
6734
9923
3334
9912
2312
출력
330
264
341
440
341

출처

JOI 2025 예선2

역링크