P6690 Linear Function.

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$.

The first line contains four integers $n, p, A, B$. The next $n$ lines each contain two integers $a_i, b_i$.

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.

**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: `` []`` Where: * ```` is the executable file of the checker; * ```` is the input file of that test case, such as ``func1.in``; * ```` is your output file for that test case, such as ``func1.out``; * ```` is the answer file of that test case (you only need to provide the first line of the output), such as ``func1.ans``; * ```` 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$ | $5$ | $\leq 3$ | $=7$ | | | $3$ | $15$ | $\leq 100$ | $=31$ | | | $4$ | $20$ | | | $A=B=1$ | | $5$ | $25$ | $\leq 20$ | | | | $6$ | $15$ | $\leq 500$ | | | | $7$ | $15$ | | | | Translated by ChatGPT 5