[POI2015]Pustynia
时间限制：10s 空间限制：128MB
题目描述
给定一个长度为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个数大（严格大于，即没有等号）。
请任意构造出一组满足条件的方案，或者判断无解。
输入格式
第一行包含三个正整数n,s,m(1<=s<=n<=100000，1<=m<=200000)。
接下来s行，每行包含两个正整数p[i],d[i](1<=p[i]<=n，1<=d[i]<=10^9)，表示已知a[p[i]]=d[i]，保证p[i]递增。
接下来m行，每行一开始为三个正整数l[i],r[i],k[i](1<=l[i]<r[i]<=n，1<=k[i]<=r[i]-l[i])，接下来k[i]个正整数x[1],x[2],...,x[k[i]](l[i]<=x[1]<x[2]<...<x[k[i]]<=r[i])，表示这k[i]个数中的任意一个都比任意一个剩下的r[i]-l[i]+1-k[i]个数大。Σk <= 300,000
输出格式
若无解，则输出NIE。
否则第一行输出TAK，第二行输出n个正整数，依次输出序列a中每个数。
样例输入
5 2 2 2 7 5 3 1 4 2 2 3 4 5 1 4
样例输出
TAK 6 7 1000000000 6 3
提示
没有写明提示
题目来源
鸣谢Claris