Problem Description

Given \( n \) linear functions \( f_i(x) = a_i x + b_i \), where \( x \) is a placeholder for formal power series.

Select \( k \) functions \( g_i(x) \) ( \( 1 \leq i \leq k \) ) from these \( n \) functions, and define the set \( H \) as the set of values obtained by multiplying powers of \( g_i \) modulo \( x^2 \). That is:

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

where \( j \) is any non-negative integer and can be different for each \( i \).

It should be noted that \( 0 \cdot x + 1 \) is always in the set \( H \) (not \( 0 \cdot x + 0 \)), even if \( k = 0 \).

Given \( A, B \), find the minimum \( k \) for all sets \( H \) such that \( A x + B \in H \).

If no such \( H \) exists, 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 an integer \( k \), representing the answer.

If a solution exists, the next \( k \) lines each contain two integers \( a, b \), which must satisfy:

\[ \left( \prod f_a(x)^b \right) \bmod x^2 = A x + B \]

The order of \( a \) can be arbitrary.

Sample Input and Output

Input Sample #1

1 997 603 648
200 61

Output Sample #1

1
1 140787

Input Sample #2

1 953 712 307
534 750

Output Sample #2

-1

Input Sample #3

3 7 6 5
3 4
5 6
4 6

Output Sample #3

2
2 5
1 20

Notes/Hints

Additional large sample cases and a checker are available for download in the attachment.

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

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

Where:

• <checker> represents the checker executable file;
• <input-file> represents the input file for the test case, such as func1.in;
• <output-file> represents your answer for the test case, such as func1.out;
• <answer-file> represents the answer file for the test case (only the first line of the output is needed), such as func1.ans;
• <report-file> is an optional parameter. If not provided, the checker will output to the terminal; otherwise, it will output to the specified file, such as report1.txt.

For all data, \( 2 \leq p \leq 10^9 \), \( p \) is guaranteed to be a prime number, \( 1 \leq n \leq 5 \times 10^3 \), \( 0 \leq a_i, A < p \), \( 1 \leq b_i, B < p \).

Detailed data constraints and agreements are as follows (blank indicates the same as the agreements for all data above):

见题面 Input 部分

见题面 Output 部分