P8060 [POI 2003] Sums

题目描述

我们给定一个整数集合 $A$。考虑一个非负整数集合 $A'$，所有属于 $A'$ 的集合的数 $x$ 满足当且仅当能被表示成一些属于 $A$ 的元素的和（数字可重复）。

比如，当 $A = \{2,5,7\}$，属于 $A'$ 的数为：$0$（$0$ 个元素的和），$2$，$4$（$2 + 2$）和 $12$（$5 + 7$ or $7 + 5$ or $2 + 2 + 2 + 2 + 2 + 2$）；但是元素 $1$ 和 $3$ 不属于 $A'$。

输入格式

第一行有一个整数 $n$，代表集合 $A$ 的元素个数。接下来每行一个数 $a_i$ 描述一个元素。$A = \{a_1,a_2,...,a_n\}$。

接下来一个整数 $k$，然后每行一个整数，分别代表 $b_1,b_2,...,b_k$。

输出格式

输出 $k$ 行。如果 $b_i$ 属于 $A'$，第 $i$ 行打印 TAK，否则打印 NIE。

输入输出样例 #1

输入 #1

3
2
5
7
6
0
1
4
12
3
2

输出 #1

TAK
NIE
TAK
TAK
NIE
TAK

说明/提示

对于所有数据，$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$。