题目描述
中二少年cenbo幻想自己有EternalFeather。他认为自己的走的每一步都是一次EmotionalFlutter。
现在cenbo要走过一条斑马线,斑马线是由n条交替的黑条和白条构成的,第一条是黑条。cenbo脚的长度是s。
cenbo要求在走的过程中,他脚的任何一部分都不能碰到象征邪恶的黑条。第一条之前和第n条之后的部分都是白色的,cenbo可以任意选择第一条之前的位置出发。
但出发位置一旦选定,之后cenbo的每一步的长度都必须是k。请你判断cenbo有没有可能在不碰到黑条的情况下通过斑马线,即走到第n条之后 。
输入格式
输入文件emotional.in有多组数据。
第一行一个整数t表示数据组数。
每组数据的第一行有三个整数s,k,n。
第二行有n个整数A1,A2,...,An,依次表示黑白条的长度。
输出格式
每组数据输出一行。
若能通过输出"TAK",否则输出"NIE"。
样例
输入样例
2
2 8 7
2 5 6 3 2 1 2
2 8 4
1 6 7 4
输出样例
TAK
NIE
提示
数据范围
30%的数据,n<=1300;
50%的数据,n<=22000;
100%的数据,2<=n<=500000,1<=s<k<=109,1<=Ai<=109,1<=t<=10。
数据有梯度。输入文件较大请使用读入优化。