변호사

Byteasar는 법률 사무소 Byteasar and Associates의 공동 소유주인 변호사다. Byteotia 변호사 협회에서 가장 많이 찾는 변호사 중 한 명이라서 늘 매우 바쁘다. 매일 여러 회의에 관여하지만, 모든 회의에 참석할 수 있는지는 이미 오래전부터 관리하지 못하고 있다. 그래서 이 혼란을 정리해 줄 비서를 고용했다. Byteasar는 매일 회의 두 개에만 참석하되, 참석하는 회의는 시작부터 끝까지 빠짐없이 함께하기로 정했다. 나머지 회의는 사무소에 넉넉히 있는 보조 변호사가 맡는다.

그런데 Byteasar의 빽빽한 일정에서는 겹치지 않는 두 회의를 찾는 일조차 어려울 때가 있다. 두 회의는 한 회의가 다른 회의가 끝난 뒤에 엄격히 늦게 시작할 때에만 겹치지 않는다고 본다. Byteasar의 비서를 도와 이 문제를 처리하는 프로그램을 작성하자.

첫째 줄에 두 정수 n과 m이 주어진다. (2 ≤ n ≤ 500,000, 1 ≤ m ≤ 20) n은 Byteasar의 일정에 있는 회의의 수, m은 일정에 포함된 날의 수다.

다음 n개 줄에 회의가 하나씩 주어진다. 각 줄은 세 정수 $a_i$, $b_i$, $d_i$로 이루어지며 (1 ≤ $a_i$ < $b_i$ ≤ 80,000,000, 1 ≤ $d_i$ ≤ m), $d_i$번째 날에 자정으로부터 정확히 $a_i$밀리초 뒤에 시작해서 자정으로부터 $b_i$밀리초 뒤에 끝나는 회의가 있다는 뜻이다.

m개 줄을 출력한다. i번째 줄에는 i번째 날에 Byteasar가 두 회의에 참석할 수 있는지를 출력한다. 불가능하면 NIE(폴란드어로 아니오) 한 단어만 출력한다. 가능하면 TAK(폴란드어로 예)을 출력하고, 이어서 Byteasar가 참석할 두 회의의 번호 p와 q를 출력한다. 회의 번호는 입력 순서대로 1부터 n까지 매긴다. p는 두 회의 중 먼저 시작하는 회의이고, q번 회의는 p번 회의가 끝난 뒤 적어도 1밀리초가 지나서 시작해야 한다. 즉 $b_p < a_q$여야 한다.

조건을 만족하는 쌍 (p, q)가 여러 개이면 p가 가장 작은 쌍을 고르고, 그중에서도 q가 가장 작은 쌍을 출력한다. p가 q보다 클 수도 있다.