Description

Bob likes Alice.

Alice and Bob want to communicate with encryption, so they designed an encryption algorithm for identity verification by themselves. You know that this encryption algorithm is not reliable, and you have intercepted the messages between Alice and Bob. Now you want to recover Alice’s secret key.

Alice and Bob agree on a large prime number $p$, a random range value $err$, and an integer secret key $x$ generated uniformly at random in $0 \sim p - 1$. Among them, the values of $p$ and $err$ are public, while the value of $x$ is only known to Alice and Bob.

When Bob wants to verify Alice’s identity, Bob generates $m$ numbers $a_i$ uniformly at random in $0 \sim p - 1$ and sends them to Alice. For each $a_i$, Alice returns to Bob the value of $a_i x$ modulo $p$. To prevent eavesdropping, Alice adds a disturbance uniformly at random in $-\lceil \frac {err}2 \rceil$ to $\lceil \frac {err}2 \rceil$ to the result.

That is, Alice returns to Bob $m$ equations of the form $a_i x + b_i \equiv c_i \pmod p$, where $b_i$ is a non-public number generated uniformly at random in $-\lceil \frac {err}2 \rceil$ to $\lceil \frac {err}2 \rceil$, $a_i$ is a randomly generated number, and $a_i, p, err, c_i$ are public numbers.

You have obtained these $m$ equations returned by Alice (that is, $m$ pairs of $a_i$ and $c_i$). You need to find the value of $x$.

Input Format

The first line contains an integer $T$, which denotes the number of test cases.

For each test case, the first line contains three integers $m, p, err$. The next $m$ lines each contain two integers $a_i, c_i$. Their meanings are the same as in the statement.

Output Format

Output $T$ lines.
For each test case, output an integer between $0$ and $p - 1$ as the answer. The testdata guarantees that a solution exists and the solution is unique.

见下发文件。该样例满足题目中提到的所有随机生成的性质。

Hint

For the first $10\%$ of the testdata, $err \le 10^6$.
For the first $20\%$ of the testdata, $err \le 10^8$.
For the first $30\%$ of the testdata, $err \le 10^{11}$.
For the first $40\%$ of the testdata, $err \le 10^{12}$.
For another $20\%$ of the testdata, $p \le 10^{16}$ and $m = 2000$.
For $100\%$ of the testdata, $10^{15} \le p \le 10^{18}$, $50 \le m \le 2000$, $1 \le err \le 0.01p$, $1 \le T \le 5$, $0 \le a_i, c_i \le p - 1$, and it is guaranteed that $p$ is prime.

Translated by ChatGPT 5