题目描述

给出$\red N$ 个不同元素，每个元素可以使用无限次数，再给出 $\red k$ 个询问，每次询问一个数 能否由这$\red N$ 个元素组成，是就输出 TAK，否则 NIE

输入格式

第一行一个数 $\red N$

接下来$\red N$ 行有$\red N$ 个数 $\red {A_1....A_n}$. 存在一个长度为$\red N$ 的序列 $\red B$，使得 $\red {\sum_{i=1}^n (A_i * B_i) = X(B_i \ge 0)}$

输出格式

对于每个询问对应输出一行，若可以构成 $\red X$，输出 TAK，否则输出 NIE

样例

输入样例

3
2
5
7
6
0
1
4
12
3
2

输出样例

TAK
NIE
TAK
TAK
NIE
TAK

提示

数据规模

$\red {20\%}$的数据，$\red {N<=100}$,询问的数不超过 $\red {1000}$. $\red {100\%}$的数据，$\red {1<=N<=5000,A_i<=50000,K<=10000,0<=X<=10^9}$