题目描述

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$ 互不相同。
保证 数据随机。