题目描述

中二少年$\red{cenbo}$幻想自己有$\red{Eternal Feather}$。他认为自己的走的每一步都是一次$\red{Emotional Flutter}$。

现在$\red{cenbo}$要走过一条斑马线，斑马线是由$\red{n}$条交替的黑条和白条构成的，第一条是黑条。$\red{cenbo}$脚的长度是$\red{s}$。

$\red{cenbo}$要求在走的过程中，他脚的任何一部分都不能碰到象征邪恶的黑条。第一条之前和第$\red{n}$条之后的部分都是白色的，$\red{cenbo}$可以任意选择第一条之前的位置出发。

但出发位置一旦选定，之后$\red{cenbo}$的每一步的长度都必须是$\red{k}$。请你判断$\red{cenbo}$有没有可能在不碰到黑条的情况下通过斑马线，即走到第$\red{n}$条之后 。

输入格式

输入文件$\red{emotional.in}$有多组数据。

第一行一个整数$\red{t }$表示数据组数。

每组数据的第一行有三个整数$\red{s, k, n}$。

第二行有$\red{n}$个整数$\red{A_1, A_2, ..., A_n，}$依次表示黑白条的长度。

输出格式

每组数据输出一行。

若能通过输出"$\red{TAK}$"，否则输出"$\red{NIE}$"。

样例

输入样例

2

2 8 7

2 5 6 3 2 1 2

2 8 4

1 6 7 4

输出样例

TAK

NIE

提示

数据范围

$\red{30\%}$的数据，$\red{n<=1300}$；

$\red{50\%}$的数据，$\red{n<=22000}$；

$\red{100\%}$的数据，$\red{2<=n<=500000, 1<=s<k<=10^9, 1<=A_i<=10^9, 1<=t<=10}$。 数据有梯度。输入文件较大请使用读入优化。