「MCOI-07」Dream and Machine Learning

Dream 构造了一个红石计算机来验证 $b^e\equiv r\pmod m$ 形式的公式。 Dream 固定了 $b$ 和 $m$ 并且构造了 $n$ 对满足以上条件的 $(e,r)$ 正整数对。 可惜，Dream 忘记了 $m$ 的具体值。现在他给了你 $b$ 和这 $n$ 对数。请替代 Dream 的计算机，回答 $q$ 组 $b^{a_i}\pmod m$ 形式的询问。

第一行三个正整数，分别代表 $b$，$n$，和 $q$。 接下来 $n$ 行，每行两个正整数，分别代表一对 $e$ 和 $r$。 接下来 $q$ 行，每行一个正整数，代表一个 $a_i$。

输出 $q$ 行，对应询问的答案。

3 8 3
108 75
616 36
220 16
37 66
114 64
514 24
1919 65
810 33
19260817
123456789
23333333

3
79
49

请见附件 sample.in

请见附件 sample.out

#### 样例 1 解释 可以唯一确定 $m=97$。 样例 1 仅仅说明题意，并不代表任何 subtask 的任何测试点。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$m\le10^3$ - Subtask 2（19 pts）：$m\le10^9$ - Subtask 3（19 pts）：$m\le10^{19}$ - Subtask 4（19 pts）：$m\le10^{29}$ - Subtask 5（19 pts）：$m\le10^{99}$ - Subtask 6（19 pts）：$m\le10^{199}$ 对于 $100\%$ 的数据，$b\in\{2,3\}$，$1\le q\le100$，$2\le e,a_i\le 10^9$，$n=10^5$。 **保证** $m$ 为质数。 **保证** 所有 $e$ 互不相同。 **保证** 数据随机。