Professor Laugh's Numbers

Professor Byteman Laugh studies prime numbers.

For a prime $p > 2$, an integer $e > 1$, and an integer $n$ with $1 \le n < p$, we say that $n$ is $(p, e)$-interesting if there exists a natural number $x$ such that $x^e \equiv n \pmod{p},$ that is, $x^e$ and $n$ leave the same remainder when divided by $p$.

Write a program that reads a prime $p$, an exponent $e$, and a sequence of numbers, and then decides for each number whether it is $(p, e)$-interesting.

The first line contains two integers separated by a single space: a prime number $p$ and an exponent $e$ ($3 \le p \le 2^{32}$, $2 \le e < 2^{32}$).

The second line contains one integer $k$, the number of queries ($1 \le k \le 15$).

Each of the next $k$ lines contains one integer $n_i$ ($1 \le n_i \le p - 1$).

Print exactly $k$ lines. Line $i$ ($1 \le i \le k$) must contain a single word: TAK (yes) if $n_i$ is $(p, e)$-interesting, or NIE (no) otherwise.