A5937 | 「ZJOI2020」密码

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$ 之间整数表示答案。数据保证有解并且解唯一。