One of the tasks in the Byteotian Intelligence Test (BIT) is to cross out numbers from an initial sequence in such a way that leaves as a result certain given sequences. Byteasar longs to become the IQ Master of Byteotia, but he is no good in this kind of tasks. But since practice makes perfect, he intends to practise a lot. So much in fact that he asks you to write a program that will facilitate the training by verifying his answers quickly.

Input

The first line of the standard input contains one integer $m$ ($1 ≤ m ≤ 1\,000\,000$). The second line holds $m$ integers $a_1,a_2,…,a_m$ ($1 ≤ a_i ≤ 1\,000\,000$ for $1 ≤ i ≤ m$), separated by single spaces, that constitute the initial sequence of the test. The third line of the input holds one integer $n$. The following $2n$ lines describe the sequences to be obtained by crossing out numbers from the initial sequence. Each sequence's description takes two successive lines. The first of these two lines contains $a_n$ integer $m_i$ ($1 ≤ m_i ≤ 1\,000\,000$). The second contains an $m_i$-element long sequence of integers $b_{i,1},b_{i,2},…,b_{i,m_i}$ ($1 ≤ b_{i,j} ≤ 1\,000\,000$ for $1 ≤ j ≤ m_i$) separated by single spaces. You may assume that the total length on given $n$ sequences does not exceed $1\,000\,000$.

Output

Your program should print out $n$ lines to the standard output. The $i$-th line (for $1 ≤ i ≤ n$) should hold one word, "TAK" (yes in Polish) if the $i$-th input sequence can be obtained by crossing out (i.e., removing) some, not necessarily contiguous, numbers from the initial sequence, or "NIE" (no in Polish) otherwise. Mind you, only the words should be printed, no quotation marks. Of course, the order of the numbers left after crossing out is important, as can be seen in the example.

Example

Input

7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4

Output

TAK
NIE
TAK
NIE