Bajtazar 正在庆祝他的十三岁生日。借此机会，他从父母那里收到了一台新电脑。这位寿星毫不犹豫地拆开了包装盒，拿起了里面的说明书。他发现这台电脑拥有 $m$ 个处理器。Bajtazar 对此感到非常高兴——他终于可以同时执行多项任务了。

事情的发展很快。片刻之后，他已经准备好了一份包含 $n$ 个任务的列表（编号从 $1$ 到 $n$），计划在他的新电脑上执行。第 $i$ 个任务需要 $c_i$ 秒的执行时间，最早可以在打开礼物后的 $p_i$ 秒开始执行。此外，它必须在打开礼物后的 $k_i$ 秒之前完成。每个任务都可以被任意次数地中断，并可以在不同处理器之间切换，但不能同时在两个或多个处理器上执行。任务切换的时间可以忽略不计。是否存在一种任务调度方案（包括中断任务和在处理器之间切换的策略），使得 Bajtazar 计划的所有任务都能按时完成？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100$)，分别表示任务数量和处理器数量。接下来的 $n$ 行描述了各个任务。第 $i$ 行包含三个整数 $p_i$、$k_i$ 和 $c_i$ ($0 \le p_i < k_i \le 10^6$; $1 \le c_i \le k_i - p_i$)，分别表示任务可以执行的时间区间的开始时间、结束时间（以打开礼物后的秒数为单位）以及完成任务所需的执行时间。

输出格式

在标准输出的一行中输出 TAK 或 NIE，取决于是否存在能够按时完成所有任务的调度方案。

样例

输入 1

3 2
3 8 3
2 5 2
3 7 3

输出 1

TAK

输入 2

2 1
0 1 1
0 1 1

输出 2

NIE