Problem Description

You are given $n$ linear functions $f_i(x) = a_i x + b_i$, where $x$ is a placeholder of a formal power series.

Choose $k$ functions $g_i(x)$ from these $n$ functions ($1 \leq i \leq k$). Define the set $H$ as the set of values obtained by taking a product of some powers of $g_i$ modulo $x^2$. That is:

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

Here, $j$ can be any non-negative integer, and different $i$ may use different $j$.

Note that $0 \cdot x + 1$ is always in the set $H$ (not $0 \cdot x + 0$). This is true even when $k = 0$.

Given $A, B$, find the minimum $k$ among all sets $H$ such that $A x + B \in H$.

If no such $H$ exists with $A x + B \in H$, output -1.

All operations are performed modulo $p$.

Input Format

The first line contains four integers $n, p, A, B$.

The next $n$ lines each contain two integers $a_i, b_i$.

Output Format

The first line contains one integer $k$, which is the answer.

If a solution exists, then the next $k$ lines each contain two integers $a, b$, and they must satisfy:

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

The order of $a$ can be arbitrary.

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

Hint

There are also two large sample tests and a checker. The download link is in the attachments.

To test your answer for a certain test case, you need to run the following command in the command line under this problem directory:

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

Where:

• <checker> is the executable file of the checker;
• <input‐file> is the input file of that test case, such as func1.in;
• <output‐file> is your output file for that test case, such as func1.out;
• <answer‐file> is the answer file of that test case (you only need to provide the first line of the output), such as func1.ans;
• <report‐file> is an optional parameter. If it is not given, the checker will output to the terminal; otherwise, it will output to that file, such as report1.txt.

Constraints: for all data, $2\leq p\leq 10^9$. It is guaranteed that $p$ is a prime. $1\leq n \leq 5 \times 10^3$, $0\leq a_i, A < p$, $1\leq b_i, B < p$.

The detailed constraints and notes are as follows (blank means the same as the constraints above):

Subtask ID	Score	$n$	$p$	Special Property
$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$

Translated by ChatGPT 5