第24回日本情報オリンピック　二次予選

2024年12月10日
情報オリンピック日本委員会

問題文

ビ太郎は，大きな円形の湖の周りに住んでいる．湖の周りの長さは 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, 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 で割ったあまりを求めるプログラムを作成せよ．

制約

• 2 ≦ N．
• N ≦ L ≦ 10⁹．
• 1 ≦ T ≦ 10⁹．
• 0 ≦ A_i ≦ L - 1 (1 ≦ i ≦ N)．
• A_i ≠ A_j (1 ≦ i < j ≦ N)．
• 1 ≦ S_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ Q．
• N + Q ≦ 100 000．
• 0 ≦ X_j ≦ L - 1 (1 ≦ j ≦ Q)．
• 1 ≦ Y_j ≦ 10⁹ (1 ≦ j ≦ Q)．
• いずれの変更が終了した時点でも，参加者は 2 人以上いる．
• いずれの変更が終了した時点でも，参加者のスタート地点は相異なる．
• 入力される値はすべて整数である．

小課題

1. (10 点) T = 1，S_i ≦ 2 (1 ≦ i ≦ N)，Y_j ≦ 2 (1 ≦ j ≦ Q)．
2. (8 点) N ≦ 2 000，Q = 1．
3. (11 点) N ≦ 2 000，Q ≦ 2 000．
4. (27 点) Q = 1．
5. (34 点) N + Q ≦ 78 000．
6. (10 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N L T
A₁ A₂ … A_N
S₁ S₂ … S_N
Q
X₁ Y₁
X₂ Y₂
:
X_Q Y_Q

出力

Q 行に出力せよ．j 行目 (1 ≦ j ≦ 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÷4 に，ゼッケン 3 を着用した参加者とゼッケン 4 を着用した参加者が同じ地点 9÷2 にいる．
2. 時刻 3÷5 に，ゼッケン 3 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 33÷5 にいる．
3. 時刻 3÷2 に，ゼッケン 1 を着用した参加者とゼッケン 4 を着用した参加者が同じ地点 0 にいる．
4. 時刻 5÷3 に，ゼッケン 1 を着用した参加者とゼッケン 6 を着用した参加者が同じ地点 2÷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 の制約を満たす．