Bajtazar is celebrating his thirteenth birthday. For this occasion, he received a new computer from his parents. Without a moment's hesitation, the birthday boy tore open the box and picked up the booklet found inside. It turned out that the computer has $m$ processors. Bajtazar was very pleased with this fact – finally, he would be able to perform many tasks simultaneously.

The further development of events did not take long. After a moment, the boy already had a prepared list of $n$ tasks (numbered from 1 to $n$) that he plans to perform on his new computer. Task number $i$ takes $c_i$ seconds and can be started no earlier than $p_i$ seconds after opening the gift. Furthermore, it must be completed no later than $k_i$ seconds after opening the gift. Each task can be interrupted any number of times and moved from one processor to another, but it cannot be executed on two or more processors simultaneously. The time taken to move a task is negligible. Does there exist a task schedule (along with a strategy for interrupting tasks and moving them between processors) that allows all the tasks planned by Bajtazar to be completed on time?

Input

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 100$), specifying the number of tasks to be performed and the number of processors, respectively. The next $n$ lines of the input describe the individual tasks. The $i$-th of these lines contains the description of task number $i$: three integers $p_i$, $k_i$, and $c_i$ ($0 \le p_i < k_i \le 10^6$; $1 \le c_i \le k_i - p_i$), representing the start and end of the time interval (given in seconds from opening the gift) during which the task can be performed, and the time required for its completion, respectively.

Output

In the single line of standard output, print TAK or NIE depending on whether there exists a task schedule that allows all tasks to be completed on time or not.

Examples

Input 1

3 2
3 8 3
2 5 2
3 7 3

Output 1

TAK

Input 2

2 1
0 1 1
0 1 1

Output 2

NIE