Polish version    English version  
  History of OI -> X OI 2002/2003


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003

Problem: Sums
Author: Krzysztof Onak

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 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 bi,
  • for each number bi 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 ai, 1 <= ai <= 50000. A = {a1a2, ..., an}, a1 < a2 < ... < an.

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 b1, b2, ..., bk.

Output

The output should consist of k lines. The i-th line should contain the word TAK ("yes" in Polish), if bi 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