题目描述

Byteasar要制订$m$天的会议计划，一共有$n$场会议。第$i$场会议开始于第$d[i]$天的第$a[i]$秒，结束于第$d[i]$天的第$b[i]$秒。 对于每一天，请找出这一天的两场会议$i,j$，使得它们不冲突，即不存在一个数$k$同时满足$a[i]\leq k\leq b[i]$以及$a[j]\leq k\leq b[j]$。

输入格式

第一行包含两个正整数$n,m$ ($2 \leq n \leq 500000, 1 \leq m \leq 20$)，表示会议的场数和天数。 接下来$n$行，每行包含三个正整数$a_i,b_i,d_i$，描述一场会议。

输出格式

输出$m$行。第$i$行输出第$i$天的答案，如果无解，输出NIE，否则输出TAK，然后输出这一天参加的两场会议的编号， 如有多组解，输出任意一组。

输入样例

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

输出样例

TAK 1 6
NIE
NIE

题目来源

鸣谢Claris上传