{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"给定一个长度为 $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\n请任意构造出一组满足条件的方案,或者判断无解。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含三个正整数 $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}\u003dd_i$,保证 $p_i$ 递增。\n\n接下来 $m$ 行,每行一开始为三个正整数 $l_i,r_i,k_i$)$1 \\leq l_i \u003c 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 \u003c x_2 \u003c ... \u003c x_{k_i} \\leq r_i$),表示这 $k_i$ 个数中的任意一个都比任意一个剩下的 $r_i-l_i+1-k_i$ 个数大。($\\sum k \\leq 3 \\times 10^5$)"}},{"title":"Output","value":{"format":"MD","content":"若无解,则输出 `NIE`。否则第一行输出 `TAK`,第二行输出 $n$ 个正整数,依次输出序列 $a$ 中每个数。"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2 2\n2 7\n5 3\n1 4 2 2 3\n4 5 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eTAK\n6 7 1000000000 6 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 1\n2 3\n3 5\n1 3 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNIE\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 1\n1 1000000000\n1 2 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNIE\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"原题名称:Pustynia。\n\n本题另外提供两组额外样例,可以在附件中下载。"}}]}