웃음 교수의 수

바이트맨 웃음 교수는 소수를 연구한다.

소수 $p > 2$, 정수 $e > 1$, 그리고 $1 \le n < p$ 인 정수 $n$ 에 대해, $x^e \equiv n \pmod{p}$ 를 만족하는 자연수 $x$ 가 존재하면 $n$ 을 $(p, e)$-흥미로운 수라고 한다. 즉, $x^e$ 와 $n$ 을 $p$ 로 나눈 나머지가 서로 같다.

소수 $p$, 지수 $e$, 그리고 여러 개의 수가 주어질 때, 각 수가 $(p, e)$-흥미로운 수인지 판정하는 프로그램을 작성하시오.

첫째 줄에 공백 하나로 구분된 두 정수, 소수 $p$ 와 지수 $e$ 가 주어진다 ($3 \le p \le 2^{32}$, $2 \le e < 2^{32}$).

둘째 줄에 질의의 개수 $k$ 가 주어진다 ($1 \le k \le 15$).

다음 $k$ 개의 줄에 각각 정수 $n_i$ 가 주어진다 ($1 \le n_i \le p - 1$).

정확히 $k$ 개의 줄을 출력한다. $i$ 번째 줄 ($1 \le i \le k$)에는 $n_i$ 가 $(p, e)$-흥미로운 수이면 TAK(예)를, 아니면 NIE(아니오)를 출력한다.