We are given a set of positive integers $A$. Consider a set of non-negative integers $A'$, such that a number $x$ belongs to $A'$ if and only if is a sum of some elements from A (the elements may be repeated). For example, if $A=\{2,5,7\}$, then sample numbers belonging to the set $A'$ are: $0$ (the sum of $0$ elements), $2$, $4$ ($2+2$) and $12$ ($5+7$ or $7+5$ or $2+2+2+2+2+2$); and the following do not belong to $A'$: $1$ and $3$.

Task

Write a program which:

• reads from the standard input the description of the set $A$ and the sequence of numbers $b_i$,
• for each number $b_i$ determines whether it belongs to the set $A'$,
• writes the result to the standard output.

Input

In the first line there is one integer $n$: the number of elements of the set $A$, $1 \le n \le 5\,000$. The following $n$ lines contain the elements of the set $A$, one per line. In the $(i+1)$-st line there is one positive integer $a_i$, $1 \le a_i \le 50\,000$. $A=\{a_1,a_2,\ldots,a_n\}$, $a_1 < a_2 < \ldots < a_n$.

In the $(n+2)$-nd line there is one integer $k$, $1 \le k \le 10\,000$. Each of the following $k$ lines contains one integer in the range from $0$ to $1\,000\,000\,000$, they are respectively the numbers $b_1,b_2,\ldots,b_k$.

Output

The output should consist of $k$ lines. The $i$-th line should contain the word TAK ("yes" in Polish), if $b_i$ belongs to $A'$, and it should contain the word NIE ("no") otherwise.

Example

Input

3
2
5
7
6
0
1
4
12
3
2

Output

TAK
NIE
TAK
TAK
NIE
TAK