【题目描述】：
    给定一个长度为n的正整数序列a，每个数都在1到10^9范围内，告诉你其中s个数，并给出m条信息，每条信息包含三个数l,r,k以及接下来k个正整数，表示a[l],a[l+1],...,a[r-1],a[r]里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大（严格大于，即没有等号）。
    请任意构造出一组满足条件的方案，或者判断无解。
【题目解法】：
    考虑对于两个点，如果需要满足a[x]<a[y]，那么连一条有向边(x,y)
    然后拓扑排序dp，令f[i]表示i的最小编号，f[i]=max(f[j]+1,val[i])
    val[i]表示一开始确定的权值，如果没有确定就为0，j是i的所有前继节点
    然后复杂度就是O(N^2)的，TLE+MLE ...
    我们考虑优化构图，显然每次连边都是一块一块的连，因此我们不妨使用线段树
    然后区间[l,r]->x，我们把[l,r]拆成log个区间连向x，然后线段树中每个儿子连向父亲
    然后对于m个限制，我们建立额外的m个点，每个限制对应的点连向每条限制中出现的k个数
    然后限制的区间向这个限制对应的点连边
    这样空间复杂度为O(M log N)
    然后注意，为了节省空间，线段树内部从儿子到父节点的边可以不连，我们只需要将他们的入度+1即可
    然后拓扑dp的时候需要特殊处理以下情况：
    1.只有连向某个序列中的点的边更新时，才需要+1
    2.如果一个已经确定的权值的边，他的max(f[j]+1)>val[i]说明无解
    复杂度O(M log N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=400005;
const int M=8000005;
const int INF=1000000000;
struct node {int id;} tree[N];
struct edge {int x,next;} b[M];
int n,m,tot,cnt,a[N],ans[N],c[N],into[N],idx[N];
int head,tail,q[N],val[N],leaf[N],fa[N]; bool flag;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void addedge(int x,int y,int flag)
{
    into[y]++; if (flag==0) return;
    ++tot; b[tot].x=y; b[tot].next=a[x]; a[x]=tot;
}
void init()
{
    n=getint(); cnt=getint(); m=getint(); tot=0; flag=true;
    for (int i=1; i<=cnt; i++) {int x=getint(); val[x]=getint();}
}
void build(int p,int l,int r)
{
    tree[p].id=++tot; fa[tot]=tree[p/2].id;
    if (p!=1) addedge(tree[p].id,tree[p/2].id,0);
    if (l==r) {idx[l]=tot; leaf[tot]=l; return;}
    int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r);
}
void modify(int p,int l,int r,int ll,int rr,int id)
{
    if (ll>rr) return; int mid=(l+r)/2;
    if ((l==ll)&&(r==rr)) {addedge(tree[p].id,id,1); return;}
    if (rr<=mid) modify(p*2,l,mid,ll,rr,id);
    else if (ll>mid) modify(p*2+1,mid+1,r,ll,rr,id);
    else modify(p*2,l,mid,ll,mid,id),modify(p*2+1,mid+1,r,mid+1,rr,id);
}
void build()
{
    build(1,1,n); cnt=tot; tot=0;
    for (int i=1; i<=m; i++)
    {
        int l=getint(),r=getint(),num=getint(); ++cnt;
        for (int j=1; j<=num; j++) c[j]=getint(); c[0]=l-1; c[++num]=r+1;
        for (int j=1; j<=num-1; j++) addedge(cnt,idx[c[j]],1);
        for (int j=1; j<=num; j++) modify(1,1,n,c[j-1]+1,c[j]-1,cnt);
    }
}
void solve()
{
    for (int i=1; i<=cnt; i++) if (into[i]==0) q[++tail]=i,ans[i]=1;
    for (head=1;head<=tail;head++)
    {
        int k=q[head];
        if ((leaf[k]!=0)&&(val[leaf[k]]!=0))
        {
            if (ans[k]>val[leaf[k]]) {flag=false; break;}
            ans[k]=max(ans[k],val[leaf[k]]);
        }
        for (int p=a[k];p;p=b[p].next)
        {
            int pp=b[p].x; --into[pp];
            if (leaf[pp]!=0) ans[pp]=max(ans[pp],ans[k]+1);
            else ans[pp]=max(ans[pp],ans[k]);
            if (into[pp]==0) q[++tail]=pp;
        }
        int pp=fa[k]; --into[pp];
        ans[pp]=max(ans[pp],ans[k]);
        if (into[pp]==0) q[++tail]=pp;
    }
    for (int i=1; i<=n; i++) if ((ans[idx[i]]==0)||(ans[idx[i]]>INF)) {flag=false; break;}
    if (!flag) {printf("NIE\n"); return;} printf("TAK\n");
    for (int i=1; i<=n; i++) printf("%d ",ans[idx[i]]); printf("\n");
}
int main()
{
    init();
    build();
    solve();
    return 0;
}