Bob 喜欢 Alice。

Alice 和 Bob 想要进行加密通信，于是他们自己设计了一套加密算法进行身份验证。你知道这个加密算法并不可靠，并截获了 Alice 和 Bob 之间的信息。现在你想要恢复出 Alice 的密钥。

Alice 和 Bob 约定了一个大质数 $p$，一个随机范围值 $err$ 和一个在 $0 \sim p−1$ 之间均匀随机生成的整数密钥 $x$。其中 $p$ 和 $err$ 的值是公开的，而 $x$ 的值只有 Alice 和 Bob 知道。

当 Bob 想要确认 Alice 的身份时，Bob 会生成 $m$ 个在 $0\sim p-1$ 之间均匀随机生成的 $a_i$ 并发给 Alice。对于每个 $a_i$，Alice 会返回给Bob $a_i x$ 模 $p$ 的值。为了防止窃听，Alice 会给结果加上一个在 $-\lceil \frac {err}2 \rceil$ 到 $\lceil \frac {err}2 \rceil$ 之间均匀随机生成的扰动。

即，Alice 会返回给 Bob $m$ 组形如 $a_i x + b_i \equiv c_i \pmod p$ 的等式，其中 $b_i$ 为一个不公开的在 $-\lceil \frac {err}2 \rceil$ 到 $\lceil \frac {err}2 \rceil$ 之间均匀随机生成的数，$a_i$ 为随机生成的数，$a_i,p,err,c_i$ 为公开的数。

你获得了 Alice 返回的这 $m$ 组等式（即 $m$ 个 $a_i$ 和 $c_i$），你需要求出 $x$ 的值。

输入格式

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，第一行输入三个整数 $m, p, err$。接下来 $m$ 行，每行两个整数 $a_i, c_i$。符号的含义和题面中相同。

输出格式

输出 $T$ 行，对于每组测试数据，输出一个 $0$ 到 $p − 1$ 之间整数表示答案。数据保证有解并且解唯一。

样例一

见附加文件中 ex_password1.in 与 ex_password1.ans。

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

限制与约定

对于前 $10\%$ 的数据，满足 $err\le 10^6$。

对于前 $20\%$ 的数据，满足 $err\le 10^8$。

对于前 $30\%$ 的数据，满足 $err \le 10^{11}$。

对于前 $40\%$ 的数据，满足 $err \le 10^{12}$。

对于另外 $20\%$ 的数据，满足 $p \le 10^{16}, m = 2000$。

对于 $100\%$ 的数据，满足 $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$，保证 $p$ 为素数。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载