
X Olympiad in Informatics 2002/2003

Problem: Sums

Author: Krzysztof Onak

We are given a set of positive integers A. Consider a set of
nonnegative integers A', such that a number x belongs
to A' if and only if x 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 <= n <= 5000. 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 <= a_{i} <= 50000.
A = {a_{1}, a_{2}, ..., a_{n}},
a_{1} < a_{2} < ... < a_{n}.
In the (n + 2)nd line there is one integer k,
1 <= k <= 10000. Each of the following
k lines contains one integer in the range from 0 to 1000000000,
they are respectively the numbers b_{1},
b_{2}, ..., b_{k}.
Output
The output should consist of k lines. The ith 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
For the following input data:
3
2
5
7
6
0
1
4
12
3
2
the correct answer is in the following output:
TAK
NIE
TAK
TAK
NIE
TAK
Print friendly version
