AT_joi2025_yo2_e 衝突 (Collision)

ビ太郎は，大きな円形の湖の周りに住んでいる．湖の周りの長さは $ L $ であり，湖の周りのある地点にはビ太郎の家がある．ビ太郎の家から湖の周りを時計回りに $ x $ ( $ 0 \leqq x < L $ ) 移動した地点を地点 $ x $ と呼ぶ．現在，湖の周りで行われるマラソン大会が企画されている． ビ太郎はマラソン大会は以下のように行われる予定であることを聞いた． - $ 0 $ から $ L - 1 $ までの番号が付けられたゼッケンが $ 1 $ 枚ずつ用意されている．マラソン大会の参加者はいずれかのゼッケンを着用する．ゼッケン $ l $ ( $ 0 \leqq l \leqq L - 1 $ ) を着用する参加者のスタート地点は地点 $ l $ となる． - マラソン大会がスタートした後， $ T $ ビョウにわたり，参加者はそれぞれの速度で湖の周りを時計回りに移動する．マラソン大会がスタートしてから， $ t $ ビョウ ( $ 0 \leqq t \leqq T $ ) 経った時点を時刻 $ t $ と呼ぶ． ビ太郎はマラソン大会の参加者名簿を持っている．現在は $ N $ 人の参加者が参加者名簿に記載されていて， $ i $ 番目の参加者 ( $ 1 \leqq i \leqq N $ ) はゼッケン $ A_i $ を着用し， $ 1 $ ビョウあたり $ S_i $ の速度で湖の周りを時計回りに移動する予定である． 参加者名簿を元に，ビ太郎はマラソン大会中に起こる**衝突**の回数を求めた．ここで，衝突とは異なる参加者 $ 2 $ 人が同じ地点にいることを指すものとする．厳密には， $ 0 \leqq p < q \leqq L - 1 $ を満たす整数 $ p, q $ と $ 0 \leqq t \leqq T $ を満たす**実数** $ t $ からなる組 $ (p, q, t) $ で，以下の条件を満たすものの個数を求めた． - ゼッケン $ p $ を着用した参加者がいる． - ゼッケン $ q $ を着用した参加者がいる． - ゼッケン $ p $ を着用した参加者とゼッケン $ q $ を着用した参加者が，時刻 $ t $ に同じ地点にいる． しかし，その後参加者名簿に $ Q $ 回の変更が行われた． $ j $ 番目 ( $ 1 \leqq j \leqq 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 $ $ \cdots $ $ A_N $ $ S_1 $ $ S_2 $ $ \cdots $ $ S_N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行に出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には $ j $ 番目の変更が終了した時点での参加者における，マラソン大会中に起こる衝突の回数を $ 1\,000\,000\,007 $ で割ったあまりを出力せよ．

### 小課題 1. ( $ 10 $ 点) $ T = 1 $ ， $ S_i \leqq 2 $ ( $ 1 \leqq i \leqq N $ )， $ Y_j \leqq 2 $ ( $ 1 \leqq j \leqq Q $ )． 2. ( $ 8 $ 点) $ N \leqq 2\,000 $ ， $ Q = 1 $ ． 3. ( $ 11 $ 点) $ N \leqq 2\,000 $ ， $ Q \leqq 2\,000 $ ． 4. ( $ 27 $ 点) $ Q = 1 $ ． 5. ( $ 34 $ 点) $ N + Q \leqq 78\,000 $ ． 6. ( $ 10 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 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. 時刻 $ \frac{1}{4} $ に，ゼッケン $ 3 $ を着用した参加者とゼッケン $ 4 $ を着用した参加者が同じ地点 $ \frac{9}{2} $ にいる． 2. 時刻 $ \frac{3}{5} $ に，ゼッケン $ 3 $ を着用した参加者とゼッケン $ 6 $ を着用した参加者が同じ地点 $ \frac{33}{5} $ にいる． 3. 時刻 $ \frac{3}{2} $ に，ゼッケン $ 1 $ を着用した参加者とゼッケン $ 4 $ を着用した参加者が同じ地点 $ 0 $ にいる． 4. 時刻 $ \frac{5}{3} $ に，ゼッケン $ 1 $ を着用した参加者とゼッケン $ 6 $ を着用した参加者が同じ地点 $ \frac{2}{3} $ にいる． 5. 時刻 $ 2 $ に，ゼッケン $ 3 $ を着用した参加者とゼッケン $ 4 $ を着用した参加者が同じ地点 $ 1 $ にいる． 6. 時刻 $ 2 $ に，ゼッケン $ 3 $ を着用した参加者とゼッケン $ 6 $ を着用した参加者が同じ地点 $ 1 $ にいる． 7. 時刻 $ 2 $ に，ゼッケン $ 4 $ を着用した参加者とゼッケン $ 6 $ を着用した参加者が同じ地点 $ 1 $ にいる． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． ### Sample Explanation 2 $ 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 $ の制約を満たす． ### Sample Explanation 3 $ 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 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 3,5,6 $ の制約を満たす． ### Constraints - $ 2 \leqq N $ ． - $ N \leqq L \leqq 10^9 $ ． - $ 1 \leqq T \leqq 10^9 $ ． - $ 0 \leqq A_i \leqq L - 1 $ ( $ 1 \leqq i \leqq N $ )． - $ A_i \neq A_j $ ( $ 1 \leqq i < j \leqq N $ )． - $ 1 \leqq S_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq Q $ ． - $ N + Q \leqq 100\,000 $ ． - $ 0 \leqq X_j \leqq L - 1 $ ( $ 1 \leqq j \leqq Q $ )． - $ 1 \leqq Y_j \leqq 10^9 $ ( $ 1 \leqq j \leqq Q $ )． - いずれの変更が終了した時点でも，参加者は $ 2 $ 人以上いる． - いずれの変更が終了した時点でも，参加者のスタート地点は相異なる． - 入力される値はすべて整数である．