[POI2015] PUS

题目描述

给定一个长度为 $n$ 的正整数序列 $a$,每个数都在 $1$ 到 $10^9$ 范围内,告诉你其中 $s$ 个数,并给出 $m$ 条信息,每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数,表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大(严格大于,即没有等号)。 请任意构造出一组满足条件的方案,或者判断无解。

输入输出格式

输入格式


第一行包含三个正整数 $n,s,m$($1 \leq s \leq n \leq 10^5$,$1 \leq m \leq 2 \times 10^5$)。接下来 $s$ 行,每行包含两个正整数 $p_i,d_i$,表示已知 $a_{p_i}=d_i$,保证 $p_i$ 递增。 接下来 $m$ 行,每行一开始为三个正整数 $l_i,r_i,k_i$)$1 \leq l_i < r_i \leq n$,$1 \leq k_i \leq r_i-l_i$),接下来 $k_i$ 个正整数 $x_1..x_2...x_{k_i}$($l_i \leq x_1 < x_2 < ... < x_{k_i} \leq r_i$),表示这 $k_i$ 个数中的任意一个都比任意一个剩下的 $r_i-l_i+1-k_i$ 个数大。($\sum k \leq 3 \times 10^5$)

输出格式


若无解,则输出 `NIE`。否则第一行输出 `TAK`,第二行输出 $n$ 个正整数,依次输出序列 $a$ 中每个数。

输入输出样例

输入样例 #1

5 2 2
2 7
5 3
1 4 2 2 3
4 5 1 4

输出样例 #1

TAK
6 7 1000000000 6 3

输入样例 #2

3 2 1
2 3
3 5
1 3 1 2

输出样例 #2

NIE

输入样例 #3

2 1 1
1 1000000000
1 2 1 2

输出样例 #3

NIE

说明

原题名称:Pustynia。 本题另外提供两组额外样例,可以在附件中下载。