A. Modular Exponentiation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For any triplet of integers $$$(b,e,m)$$$ where $$$0\le b \lt m$$$ and $$$m$$$ is prime, there exists exactly one $$$r$$$ where $$$0\le r \lt m$$$ such that

$$$$$$b^e\equiv r\pmod m$$$$$$

Dream fixed $$$b$$$ and $$$m$$$ ($$$m$$$ prime) and generated $$$n$$$ values of $$$e$$$ along with the $$$n$$$ corresponding solutions for $$$r$$$. As such, Dream now has $$$n$$$ pairs $$$(e,m)$$$. Dream also has $$$q$$$ values of $$$e$$$, respectively stored as $$$a_1,a_2,\dots,a_q$$$, that he wishes to calculate the corresponding $$$r$$$ for.

Unfortunately, Dream completely forgot the value of $$$m$$$. Given the $$$b$$$, the $$$n$$$ pairs of $$$(e,r)$$$, and the $$$q$$$ values $$$a_1,a_2,\dots,a_q$$$, please calculate $$$b^{a_i}\bmod m$$$.

Input

The first line contains thee integers $$$b$$$, $$$n$$$, and $$$q$$$ ($$$2\le b\le 3$$$, $$$n=10^5$$$, $$$1\le q\le 100$$$).

Each of the next $$$n$$$ lines contain two integers $$$e$$$ and $$$r$$$ ($$$2\le e\le 10^9$$$).

Each of the following $$$q$$$ lines contain one integer $$$a_i$$$ ($$$2\le a_i\le 10^9$$$).

The test data guarantees that all $$$e$$$ are pairwise distinct and that exactly one $$$m$$$ can be determined by the given $$$e$$$ and $$$r$$$.

The test data further guarantees that all $$$e$$$ are randomly sampled between $$$2$$$ and $$$10^9$$$ under the condition that all $$$e$$$ are pairwise distinct.

Output

Output $$$q$$$ lines, each line containing one integer, corresponding to the value of $$$r$$$ such that $$$0\le r \lt m$$$ and $$$b^{a_i}\equiv r\pmod m$$$.

Scoring
  • In the first subtask, worth $$$5$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^3$$$.
  • In the second subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^9$$$.
  • In the third subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{19}$$$.
  • In the fourth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{29}$$$.
  • In the fifth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{99}$$$.
  • In the sixth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{199}$$$.
Example
Input
3 8 3
108 75
616 36
220 16
37 66
114 64
514 24
1919 65
810 33
19260817
123456789
23333333
Output
3
79
49
Note

It can be determined that $$$97$$$ is the only prime that satisfies the given conditions.

This sample does not correspond to any testcase in the actual test data.

Note that CPython may be faster than PyPy.