Discrete Logarithm with Primitive Root

Given a prime number \(P\) and one of its primitive roots \(g\), you are asked to solve the discrete logarithm problem. For each query, given an integer \(y\), find the smallest nonnegative integer \(x\) such that \(g^x \equiv y \pmod{P}\). If no such \(x\) exists, output -1.

inputFormat

The first line contains two integers: a prime number \(P\) and its primitive root \(g\).

The second line contains an integer \(q\) representing the number of queries.

Each of the next \(q\) lines contains a single integer \(y\).

outputFormat

For each query, output the smallest nonnegative integer \(x\) such that \(g^x \equiv y \pmod{P}\). If no such \(x\) exists, output -1.

sample

7 3
3
1
3
2

0
1
2