从 Bythad 到 Bytara 的路线穿过大 Byteotian 沙漠。这段旅程非常艰辛，尤其是因为沿途只有 $s$ 口水井。Byteotia 的统治者深知国家的繁荣依赖于交通路线，因此决定在这条特定的路线上挖掘新的水井。从 Bythad 到 Bytara 的距离为 $n+1$ 个字节英里（bytemiles），在距离 Bythad 的每一个整数倍字节英里处，要么已经有一口水井，要么可以挖掘一口新井。然而，水位越低，挖掘水井的难度和成本就越高。

因此，统治者委托皇家地质学家 Byteasar 对各种方案进行勘测。Byteasar 拥有通过卫星网络获得的 $m$ 次测量数据。遗憾的是，卫星收集的信息并没有直接提供水位数据。每次测量都是针对路线的一个连续片段，仅说明在该片段的某些点上，水位低于其余点。此外，已知每个点的水位都在地表以下 $1$ 到 $10^9$ 字节米（bytometers）之间。

请帮助 Byteasar 确定沿途每个点的可能水位。卫星数据可能存在矛盾。

输入格式

标准输入的第一行包含三个整数 $n, s, m$ ($1 \le s \le n \le 100\,000, 1 \le m \le 200\,000$)，用空格分隔，分别表示沿途的水井数量和卫星测量次数。

接下来的 $s$ 行描述水井：第 $i$ 行包含两个整数 $p_i$ 和 $d_i$ ($1 \le p_i \le n, 1 \le d_i \le 1\,000\,000\,000$)，表示第 $i$ 口水井位于距离 Bythad $p_i$ 字节英里处，深度为 $d_i$ 字节米（即该处的水位在地表以下 $d_i$ 字节米）。水井按 $p_i$ 的递增顺序给出。

接下来的 $m$ 行描述卫星测量：第 $i$ 行包含三个整数 $l_i, r_i$ 和 $k_i$ ($1 \le l_i < r_i \le n, 1 \le k_i \le r_i - l_i$)，随后是一个包含 $k_i$ 个整数的序列 $x_1, x_2, \dots, x_{k_i}$ ($l_i \le x_1 < x_2 < \dots < x_{k_i} \le r_i$)。这些数据说明测量是在从 $l_i$ 到 $r_i$ 的路段（包含这两个端点）上进行的，结果表明在点 $x_1, \dots, x_{k_i}$ 处的每一个水位都严格低于该区间内其余（整数）点处的水位，即集合 $\{l_i, \dots, r_i\} \setminus \{x_1, \dots, x_{k_i}\}$ 中的点。所有 $k_i$ 的总和不超过 $200\,000$。

在总分占比 60% 的测试中，满足附加条件 $n, m \le 1000$。在总分占比 30% 的测试中，所有 $k_i$ 的总和不超过 $1000$。

输出格式

如果测量数据存在矛盾，标准输出的第一行应包含一个单词 NIE（波兰语中的“否”）。否则，输出的第一行应包含单词 TAK（波兰语中的“是”），第二行应包含一个由 $n$ 个整数组成的序列，每个整数在 $1$ 到 $1\,000\,000\,000$ 的范围内，表示从 Bythad 开始沿途各点处的水位深度。如果存在多个解，程序可以任意选择一个。

样例

样例输入 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