题目描述

给定一个长度为$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$。接下来$s$行，每行包含两个正整数$p[i],d[i]$，表示已知$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]$个数大。

输出

若无解，则输出$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

提示

【数据规模及约定】 对于100%的数据，$1≤s≤n≤100000，1≤m≤200000，Σk≤300,000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。