题目背景

译自 日本情報オリンピック 第4回女性部門 (JOIG 2023/2024) 春季トレーニング R1T2。

图：年轮蛋糕。バームクーヘン = baumkuchen，即树木（德语 baum）+ 蛋糕（德语 kuchen）。图源百度百科。

题目描述

葵计划举办一场派对，共有 $K$ 人参加，编号 $1\sim K$。

众人将分享一个环形的年轮蛋糕。蛋糕的圆周上均匀刻有 $K \times L$ 个切缝，蛋糕只能沿切缝分割。

将切缝按顺时针编号 $1\sim K\times L$，切缝 $i$ 和切缝 $\left(i\bmod KL\right) +1$ 之间的区域叫做第 $i$ 个部分。

分割规则如下：

1. 选择 $K$ 个切缝切割，将蛋糕分为 $K$ 块，每个块包含恰好 $L$ 个连续的部分。
2. 把 $K$ 块蛋糕分给 $K$ 个人，要求每个人都恰好分到一块蛋糕。

现在有 $Q$ 条限制，第 $j$ 条限制要求第 $X_j$ 个部分必须被分配给第 $Y_j$ 个人。保证每个部分 $X_j$ 只会在限制中出现一次。

对于 $i=1,2,\cdots,Q$，求出有多少种切蛋糕和分蛋糕的方案满足前 $i$ 条限制，对给定的素数 $P$ 取模。

两个方案不同，当且仅当存在一个人，他在这两个方案中拿到了不同的蛋糕块。

输入格式

如下所示：

$K$ $L$
$P$
$Q$ $X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$

输出格式

输出 $Q$ 行，每行一个整数，表示满足前 $i$ 条限制的方案数量对 $P$ 取模后的结果。

3 2
998244353
2
1 2
6 2

4
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

50400
40320
5760
960
48
48
12
0
0
0

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

2903040
322560
40320
5760
600
240
48
0
0
0

提示

样例解释

样例 $1$ 解释

$i=1$ 时，要求将包含第 $1$ 个部分的块分给第 $2$ 个人，有 $4$ 个方案。举例：

1. 沿切缝 $1$、$3$、$5$ 切割蛋糕；
2. 分配方式：
   • 第 $1$ 个人：第 $3,4$ 个部分；
   • 第 $2$ 个人：第 $1,2$ 个部分；
   • 第 $3$ 个人：第 $5,6$ 个部分。

$i=2$ 时，在 $i=1$ 的基础上额外要求将包含第 $6$ 个部分的块分配给第 $2$ 个人，有 $2$ 个方案。举例：

1. 沿切缝 $2$、$4$、$6$ 切割蛋糕；
2. 分配方式：
   • 第 $1$ 个人：第 $4,5$ 个部分；
   • 第 $2$ 个人：第 $6,1$ 个部分；
   • 第 $3$ 个人：第 $2,3$ 个部分。

该样例满足所有子任务的限制。

样例 $2$ 解释

该样例满足所有子任务的限制。

样例 $3$ 解释

该样例满足子任务 $2\sim 6$ 的限制。

数据范围

• $2\le K\le 2\times 10^5$；
• $1\le L\le 2\times 10^5$；
• $10^8\lt P\lt 10^9$；
• $P$ 是素数；
• $1\le Q\le 2\times 10^5$；
• $\forall 1\le j\le Q$，$1\le X_j\le KL$；
• $\forall 1\le j\lt k\le Q$，$X_j\neq X_k$；
• $\forall 1\le j\le Q$，$1\le Y_j\le k$；
• 输入的值全部是整数。

子任务

1. （13pts）$K\le 8$，$L\le 10$，$Q\le 10$。
2. （14pts）$K\le 100$，$L\le 100$，$Q\le 100$。
3. （18pts）$K\le 400$，$L\le 400$，$Q\le 400$。
4. （17pts）$K\le 2\, 500$，$L\le 2\, 500$，$Q\le 2\, 500$；
5. （28pts）$K\le 40$；
6. （10pts）无额外限制。

翻译来自 DeepSeek-R1 并经过人工微调。