P7328 "MCOI-07" Dream and Machine Learning

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$.

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 $q$ lines, each being the answer to the corresponding query.

#### 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