Byteasar 是一位律师，也是律师事务所 Byteasar and Associates 的合伙人。他是 Byteotian 律师协会中最炙手可热的成员之一。不出所料，他总是极其忙碌。他每天都要参加许多会议，早已无法掌控自己是否能够参加所有会议。因此，他雇了一位秘书，其工作是帮助他控制这种混乱。Byteasar 决定每天只参加两场会议，但他必须全程参与，即从会议开始到结束。其余的会议将由他办公室里众多的助手来处理。

不幸的是，在 Byteasar 繁忙的日程中，有时甚至很难找到两场不重叠的会议。我们假设两场会议不重叠，当且仅当其中一场会议在另一场会议结束后才开始。请帮助 Byteasar 的秘书编写一个程序来解决这个问题。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000$, $1 \le m \le 20$)，分别表示 Byteasar 日程表中的会议总数和包含的天数。

接下来的 $n$ 行，每行描述一场会议。每场会议由三个整数 $a_i, b_i, d_i$ ($1 \le a_i < b_i \le 80\,000\,000$, $1 \le d_i \le m$) 组成，表示在第 $d_i$ 天，Byteasar 有一场会议，该会议在午夜后 $a_i$ 毫秒开始，在午夜后 $b_i$ 毫秒结束。

输出格式

你的程序应输出 $m$ 行。第 $i$ 行应包含关于 Byteasar 是否能在第 $i$ 天参加两场会议的信息。如果无法参加，则输出一个单词 “NIE”（波兰语中的“不”）。否则，输出单词 “TAK”（波兰语中的“是”），随后输出他可以参加的两场会议的编号。会议编号从 $1$ 到 $n$，按照输入顺序排列。这两场会议中的第一场应更早开始。第二场会议的开始时间应至少比第一场会议的结束时间晚一毫秒。

如果有多种正确答案，输出其中任意一种即可。

样例

样例输入 1

6 3
3 5 1
2 4 2
1 8 1
6 7 3
3 5 2
7 12 1

样例输出 1

TAK 1 6
NIE
NIE