Description

Dream built a redstone computer to verify formulas of the form $b^e\equiv r\pmod m$.
Dream fixed $b$ and $m$, and constructed $n$ pairs of positive integers $(e,r)$ that satisfy the condition above.
Unfortunately, Dream forgot the exact value of $m$. Now he gives you $b$ and these $n$ pairs. Please replace Dream's computer and answer $q$ queries of the form $b^{a_i}\pmod m$.

Input Format

The first line contains three positive integers, representing $b$, $n$, and $q$.
The next $n$ lines each contain two positive integers, representing a pair $e$ and $r$.
The next $q$ lines each contain one positive integer, representing an $a_i$.

Output Format

Output $q$ lines, each being the answer to the corresponding query.

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

Hint

Explanation for Sample 1

You can uniquely determine that $m=97$.
Sample 1 only explains the problem statement, and does not represent any test point of any subtask.

Constraints

This problem uses bundled testcases.

• 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}$

For $100\%$ of the testdata, $b\in\{2,3\}$, $1\le q\le100$, $2\le e,a_i\le 10^9$, and $n=10^5$.
It is guaranteed that $m$ is a prime number.
It is guaranteed that all $e$ are pairwise distinct.
It is guaranteed that the testdata is random.

Translated by ChatGPT 5