#2707. Emotional Flutter

Emotional Flutter

题目描述

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

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

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

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

输入格式

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

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

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

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

输出格式

每组数据输出一行。

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

样例

输入样例

2

2 8 7

2 5 6 3 2 1 2

2 8 4

1 6 7 4

输出样例

TAK

NIE

提示

数据范围

30%\red{30\%}的数据,n<=1300\red{n<=1300}

50%\red{50\%}的数据,n<=22000\red{n<=22000}

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