[Poi2003]Sums

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

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

输入格式

第一行有一个整数 $n$，代表集合 $A$ 的元素个数。

接下来 $n$ 行每行一个数 $a_i$ 描述一个元素，其中 $A=\{a_1, a_2, \dots, a_n\}$，且 $a_1<a_2<\dots<a_n$。

接下来一个整数 $k$，再接下来 $k$ 行每行一个整数，分别代表 $b_1, b_2, \dots, b_k$。

输出格式

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

样例输入

3
2
5
7
6
0
1
4
12
3
2

样例输出

TAK
NIE
TAK
TAK
NIE
TAK

样例解释

此时 $A=\{2,5,7\}$，六个询问依次为 $0, 1, 4, 12, 3, 2$：

• $0$ 是 $0$ 个元素之和，属于 $A'$；
• $1$ 无法表示；
• $4=2+2$；
• $12=5+7$；
• $3$ 无法表示；
• $2$ 本身就是 $A$ 中的元素。

数据范围

• $1\le n\le 5000$；
• $1\le a_i\le 50000$；
• $1\le k\le 10^4$；
• $0\le b_i\le 10^9$。

来源与许可

本题为 POI 2003 试题「Sums」，题面与测试数据整理自 BZOJ 2612。

样例 1

输入

3


2
5
7
6
0
1
4
12
3
2

输出

TAK
NIE
TAK
TAK
NIE
TAK