Background

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.

Problem Description

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

Input Format

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 Format

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

3 31
3
27 16
21 3
9 26

4
21
25

Hint

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

For $100\%$ of the testdata, $2\le A,B<P<2^{31}$, $2\le g<20$, $1\le n\le 20$.

Statement fixed by @Starrykiller.

Translated by ChatGPT 5