The Lawyer

Byteasar is an advocate and co-owner of the law firm Byteasar and Associates. He is one of the most sought-after members of the Byteotian Bar, so he is always extremely busy. Every day he is involved in a number of meetings, and he stopped keeping track long ago of whether he can attend all of them. He therefore hired a secretary whose job is to bring this chaos under control. Byteasar decided that every day he will take part in two meetings only, but his participation will be complete, from the very beginning to the very end. Assistants, of whom the office has plenty, take care of the remaining meetings.

Unfortunately, in Byteasar's busy schedule it is sometimes hard even to find two meetings that do not overlap. Two meetings do not overlap if one of them starts strictly after the other has finished. Help Byteasar's secretary and write a program that deals with this problem.

The first line contains two integers n and m (2 ≤ n ≤ 500,000, 1 ≤ m ≤ 20): the number of meetings in Byteasar's schedule and the number of days it covers.

Each of the next n lines describes one meeting as three integers $a_i$, $b_i$, $d_i$ (1 ≤ $a_i$ < $b_i$ ≤ 80,000,000, 1 ≤ $d_i$ ≤ m): on day $d_i$ Byteasar has a meeting that starts exactly $a_i$ milliseconds after midnight and ends $b_i$ milliseconds after midnight.

Print m lines. The i-th line states whether Byteasar can attend two meetings on day i. If he cannot, print the single word NIE (Polish for no). Otherwise print the word TAK (Polish for yes) followed by the numbers p and q of the two meetings he attends. Meetings are numbered from 1 to n in input order. Meeting p is the one that starts earlier, and meeting q must start at least one millisecond after meeting p ends, that is, $b_p < a_q$.

If several pairs (p, q) satisfy these conditions, print the pair with the smallest p, and among those the pair with the smallest q. Note that p may be larger than q.