P4454 [CQOI2018] Cracking the D-H Protocol

The Diffie-Hellman key exchange protocol is a simple and effective method for key exchange. It allows two parties to agree on a secure key $K$ over an insecure (possibly eavesdropped) channel without a pre-shared key, and then use it to encrypt subsequent communication.

Assume the two parties are named Alice and Bob. The protocol works as follows (where $\bmod$ denotes the modulo operation): 1. The protocol specifies a fixed prime $P$ and a primitive root modulo $P$, $g$. The values $\boldsymbol P$ and $\boldsymbol g$ are public and do not need to be kept secret. 2. Alice generates a random number $a$, computes $A=g^a \bmod P$, and sends $A$ to Bob over the insecure channel. 3. Bob generates a random number $b$, computes $B=g^b \bmod P$, and sends $B$ to Alice over the insecure channel. 4. Bob computes the key $K=A^b \bmod P$ from the received $A$, and Alice computes $K=B^a \bmod P$ from the received $B$. 5. Both parties obtain the same $K$, namely $g^{ab} \bmod P$. $K$ is the encryption key for later communication. In this process, only $A$ and $B$ can be eavesdropped, while $a$, $b$, and $K$ remain secret. Given the four numbers $A$, $B$, $P$, and $g$, it is not easy to compute $K$, so $K$ can serve as a secure key. Of course, security is relative. The security of the protocol depends on the sizes of the values. Typically, $a$, $b$, and $P$ are chosen as large integers with hundreds of bits to prevent compromise. However, if Alice and Bob are lazy in programming and, to avoid implementing big-integer arithmetic, choose values less than $2^{31}$, then cracking their key becomes relatively easy. Given $n$ pairs of eavesdropped $A$ and $B$, you need to try to crack the key $K$.

The first line contains two space-separated positive integers $g$ and $P$. The second line contains a positive integer $n$, indicating that Alice and Bob performed $n$ sessions (i.e., ran the protocol $n$ times). Then follow $n$ lines. Each line contains two space-separated positive integers $A$ and $B$, representing the eavesdropped values $A$ and $B$ for one session.

Output $n$ lines. Each line contains a single positive integer $K$, which is the key you cracked for that session.

For $30\%$ of the testdata, $2\le A,B,P\le 1000$. For $100\%$ of the testdata, $2\le A,B