P8060 [POI 2003] Sums

You are given a set of integers $A$. Consider a set of non-negative integers $A'$. A number $x$ belongs to $A'$ if and only if it can be represented as the sum of some elements from $A$ (elements may be used repeatedly). For example, if $A = \{2,5,7\}$, then numbers in $A'$ include: $0$ (the sum of $0$ elements), $2$, $4$ ($2 + 2$), and $12$ ($5 + 7$ or $7 + 5$ or $2 + 2 + 2 + 2 + 2 + 2$). However, $1$ and $3$ do not belong to $A'$.

The first line contains an integer $n$, the number of elements in set $A$. Each of the next lines contains one integer $a_i$, describing an element. $A = \{a_1,a_2,...,a_n\}$. Then an integer $k$ follows, and each of the next lines contains one integer, representing $b_1,b_2,...,b_k$.

Output $k$ lines. If $b_i$ belongs to $A'$, print `TAK` on the $i$-th line; otherwise, print `NIE`.

For all testdata, $1 \le n \le 5 \times 10^3$, $1 \le k \le 10^4$, $1 \le a_1 < a_2 < ... < a_n \le 5 \times 10^4$, $0 \le b_i \le 10^9$. Translated by ChatGPT 5