Byteasar要制订m天的会议计划，一共有n场会议，第i场会议开始于第d[i]天的第a[i]秒，结束于第d[i]天的第b[i]秒。

对于每一天，请找出这一天的两场会议i,j，使得它们不冲突，即不存在一个数k同时满足a[i]<=k<=b[i]以及a[j]<=k<=b[j]。

 

第一行包含两个正整数n,m(2<=n<=500000,1<=m<=20)，表示会议的场数和天数。

接下来n行，每行包含三个正整数a[i],b[i],d[i](1<=a[i]<b[i]<=80000000,1<=d[i]<=m)，描述一场会议。

 

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

如有多组解，输出任意一组。

 

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define ren for(int i=first[x];i!=-1;i=next[i])

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

const int maxn=;

struct Conference {int s,t;}A[maxn];

int first[],next[maxn],e,num[maxn];

void Add(int x,int v) {

    num[++e]=v;next[e]=first[x];first[x]=e;

}

int n,m;

int main() {

    n=read();m=read();

    rep(i,,n) A[i].s=read(),A[i].t=read(),Add(read(),i);

    rep(i,,m) {

        int a=num[first[i]],b=a,cnt=;

        for(int j=first[i];j;j=next[j]) {

            if(A[num[j]].s>A[a].s) a=num[j];

            if(A[num[j]].t<A[b].t) b=num[j];

            cnt++;

        }

        if(cnt<||A[a].s<=A[b].t) puts("NIE");

        else printf("TAK %d %d\n",a,b);

    }

    return ;

}