题目描述

给定 $n$ 个一次函数 $f_i(x) = a_ix + b_i$，其中 $x$ 为形式幂级数的占位符。

从这 $n$ 个中选出 $k$ 个 $g_i(x)$ （$1\leq i \leq k$），定义集合 $H$ 为 $g_i$ 的若干次幂的乘积模 $x^2$ 的值所构成的集合。即：

$$H=\left\{\prod_{i=1}^k g_i(x)^j\bmod x^2\middle|0 \leq a, b < p \right\} $$

其中 $j$ 是任意非负整数且对于每个 $i$ 可以有不同的 $j$。

需要注意的是，$0\cdot x+1$ 始终在集合 $H$ 中（而非 $0 \cdot x + 0$），即使 $k = 0$ 也是如此。

给定 $A, B$，求出所有满足 $Ax+B\in H$ 的集合 $H$ 的 $k$ 的最小值。

若不存在 $H$ 使得 $Ax+B\in H$，输出 -1。

所有运算均在模 $p$ 意义下进行。

输入格式

第一行四个整数 $n, p, A, B$。

接下来 $n$ 行，每行两个整数 $a_i, b_i$。

输出格式

第一行一个整数 $k$，表示答案。

若存在方案，接下来 $k$ 行，每行两个整数 $a, b$，需满足

$$\left(\prod f_a(x)^b\right)\bmod x^2=Ax + B$$

$a$ 的顺序可任意。

1 997 603 648
200 61

1
1 140787

1 953 712 307
534 750

-1

3 7 6 5
3 4
5 6
4 6

2
2 5
1 20

提示

另有两组大样例与 checker，下载地址见附件。

要测试你某个测试点的答案，你需要在你本题目录下的命令行中执行：

<checker> <input‐file> <output‐file> <answer‐file> [<report‐file>]

其中：

• <checker> 表示校验器可执行文件；
• <input‐file> 表示该测试点的输入文件，如 func1.in；
• <output‐file> 表示该测试点你的答案，如 func1.out；
• <answer‐file> 表示该测试点的答案文件（只需要提供输出的第一行），如 func1.ans；
• <report‐file> 为可选参数，如果没有给定该参数，校验器将输出至终端；否则将输出至该文件，如 report1.txt。

对于所有数据，$2\leq p\leq 10^9$，保证 $p$ 为质数，$1\leq n \leq 5 \times 10^3$，$0\leq a_i, A < p$，$1\leq b_i, B < p$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

子任务编号	分值	$n$	$p$	特殊性质
$1$	$5$	$=1$	$\leq 1000$
$2$		$\leq 3$	$=7$
$3$	$15$	$\leq 100$	$=31$
$4$	$20$			$A=B=1$
$5$	$25$	$\leq 20$
$6$	$15$	$\leq 500$
$7$