B - バームクーヘン 2 (Baumkuchen 2) 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

葵はパーティーを開催しようと計画している.このパーティーには葵を含めた K 人が参加予定であり,参加者には 1 から K までの番号が付けられている.

パーティーでは K 人で 1 個のバームクーヘンを食べる.バームクーヘンは円筒形のお菓子である.K 人に分けるために,葵は半径方向に刃を K 回入れて,これを K 個の等しい大きさのピースに切り分けなければならない.ただしこのバームクーヘンは本物の木材のように固いので,刃を入れるのは簡単ではない.そのためこのバームクーヘンにはあらかじめ K \times L 個の切れ込みが均等に入っており,葵は切れ込みがある位置でのみ切ることができる.切れ込みに 1 から KL まで時計回りに番号をふったとき,整数 i (1 \leqq i \leqq KL - 1) に対し,切れ込み i と切れ込み i + 1 の間の部分をパーツ i と呼ぶ.また,切れ込み KL と切れ込み 1 の間の部分をパーツ KL と呼ぶ.

葵は以下の手順に沿って,バームクーヘンを分けようとしている.

  1. K 個の切れ込みに沿ってバームクーヘンを切り,L 個のパーツからなるピース K 個に分ける.
  2. 各参加者にピースを 1 個ずつ割り当てる.ただし,1 個のピースが 2 人以上の参加者に割り当てられてはいけない.

現在,葵はバームクーヘンを分ける手順を決めていない.これから,Q 回にわたり参加者が要望を葵に伝える.j 回目 (1 \leqq j \leqq Q) に葵に伝える要望は,以下のようなものである.

  • 各参加者にピースを割り当てた後に,パーツ X_{j} を含むピースが参加者 Y_{j} に割り当てられているようにしたい.

ただし,すでに要望で指定されたパーツが新たに指定されることはない.

葵は,各要望が伝えられた時点において,その時点までのすべての要望を満たすような手順が何通りあるかを求めたい.ここで,2 つの手順が異なるとは,割り当てられている参加者が異なるようなパーツがあることとする.

バームクーヘンと参加者の要望の情報と素数 P が与えられたとき,各要望が伝えられた時点において,その時点までのすべての要望を満たすような手順の個数を P で割った余りを求めるプログラムを作成せよ.

入力

入力は以下の形式で標準入力から与えられる.

K L
P
Q
X_{1} Y_{1}
X_{2} Y_{2}
\vdots
X_{Q} Y_{Q}

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,j 回目の要望が伝えられた時点において,その時点までのすべての要望を満たすような手順の個数を P で割った余りを出力せよ.

制約

  • 2 \leqq K \leqq 200\,000.
  • 1 \leqq L \leqq 200\,000.
  • 10^{8} < P < 10^{9}.
  • P は素数である.
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq X_{j} \leqq KL (1 \leqq j \leqq Q).
  • X_{j} \ne X_{k} (1 \leqq j < k \leqq Q).
  • 1 \leqq Y_{j} \leqq K (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (13 点) K \leqq 8,L \leqq 10,Q \leqq 10.
  2. (14 点) K \leqq 100,L \leqq 100,Q \leqq 100.
  3. (18 点) K \leqq 400,L \leqq 400,Q \leqq 400.
  4. (17 点) K \leqq 2\,500,L \leqq 2\,500,Q \leqq 2\,500.
  5. (28 点) K \leqq 10.
  6. (10 点) 追加の制約はない.

入力例 1

3 2
998244353
2
1 2
6 2

出力例 1

4
2

1 回目の要望はパーツ 1 を含むピースが参加者 2 に割り当てられているようにしたいというものである.この時点までのすべての要望を満たすような手順の個数は 4 通りである.例えば,以下のような手順が考えられる.

  1. 切れ込み 1, 3, 5 に沿ってバームクーヘンを切り分ける.
  2. 参加者 1 にパーツ 3, 4 からなるピースを割り当てる.参加者 2 にパーツ 1, 2 からなるピースを割り当てる.参加者 3 にパーツ 5, 6 からなるピースを割り当てる.

2 回目の要望はパーツ 6 を含むピースが参加者 2 に割り当てられているようにしたいというものである.この時点までのすべての要望を満たすような手順の個数は 2 通りである.例えば,以下のような手順が考えられる.

  1. 切れ込み 2, 4, 6 に沿ってバームクーヘンを切り分ける.
  2. 参加者 1 にパーツ 4, 5 からなるピースを割り当てる.参加者 2 にパーツ 6, 1 からなるピースを割り当てる.参加者 3 にパーツ 2, 3 からなるピースを割り当てる.

この入出力例はすべての小課題の制約を満たす.

入力例 2

8 10
304623133
10
8 8
6 8
51 1
36 5
10 7
38 5
68 3
57 4
76 3
19 2

出力例 2

50400
40320
5760
960
48
48
12
0
0
0

この入出力例はすべての小課題の制約を満たす.

入力例 3

10 8
446958661
10
26 5
49 9
37 6
10 1
15 3
29 5
69 2
2 1
25 5
12 1

出力例 3

2903040
322560
40320
5760
600
240
48
0
0
0

この入出力例は小課題 2, 3, 4, 5, 6 の制約を満たす.


出典

JOIG 2023/2024 春季トレーニング Contest Day1