Time Limit: 3000 MS Memory Limit: 65536 K

## Description

Professor Byteman Laugh has been given a unique chance.
He has been told that he could get a million dollars for his
research from Foundation for Helping Wicked Byteprofessors.
The professor always does his best to make his research
interesting. Now it is time for the society to grade the professor's work.
However, it is not so easy. The professor has only one week before
he will have to present the results of his research.
As every scientist, professor Laugh is a little bit absent-minded.
He has lost the results somewhere,
so he is asking you to write a program which reproduces them.
Professor Laugh does not like to bore his friends and colleagues.
Therefore, he is not interested in ordinary integrals,
but in thrilling and mind-blowing prime numbers.
For a prime number^{1} p greater than 2 ,
an integer e greater than 1 and an integer n less than p
the professor says that n is (p,e)-interesting if there is
a natural number x such that, x^{e}¡Ôn(mod p).
In other words x^{e} and n give the same remainder
when divided by p.
Write a program which:
reads a prime number p, an exponent e and a sequence of numbers;
tests each number in this sequences if it is (p,e)-interesting;
writes the result.
## Input

The first line contains two integers separated by a single space:
a prime number p and a number e (3¡Üp¡Ü2^{32},2¡Üe<2^{32}).
The second line contains one integer k, i.e. the number of cases (1¡Ük¡Ü15).
Each of next k lines contains one integer. The i-th of these lines contains
a number n_{i}, 1¡Ün_{i}¡Üp-1.
## Output

Your program should write exactly k lines. The line number i(1¡Üi¡Ük)
should contain one word: TAK (i.e. yes in Polish) if n_{i}
is (p,e)-interesting, NIE (i.e. no in Polish) if it is not.
## Sample Input

17 2
5
1
9
3
7
6
## Sample Output

TAK
TAK
NIE
NIE
NIE
## HINT

We say that an integer is prime if it is greater than 1 and it has no positive integer divisors other than 1 and itself.