Description

Given a positive integer sequence $a$ of length $n$, where each number is in the range $1$ to $10^9$. You are told $s$ of the numbers, and given $m$ pieces of information. Each piece contains three numbers $l, r, k$ followed by $k$ positive integers, meaning that among $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$, each of the values at those $k$ positions is strictly greater than each of the values at the remaining $r - l + 1 - k$ positions (strictly greater; no equality).

Construct any sequence that satisfies all the conditions, or determine that there is no solution.

Input Format

The first line contains three positive integers $n, s, m$ ($1 \leq s \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$). The next $s$ lines each contain two positive integers $p_i, d_i$, meaning $a_{p_i} = d_i$. It is guaranteed that the $p_i$ are in increasing order.

The next $m$ lines: each line begins with three positive integers $l_i, r_i, k_i$ ($1 \leq l_i < r_i \leq n$, $1 \leq k_i \leq r_i - l_i$), followed by $k_i$ positive integers $x_1, x_2, \ldots, x_{k_i}$ ($l_i \leq x_1 < x_2 < \cdots < x_{k_i} \leq r_i$), indicating that in $a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}$, each of these $k_i$ positions has a value strictly greater than each of the other $r_i - l_i + 1 - k_i$ positions. ($\sum k_i \leq 3 \times 10^5$.)

Output Format

If there is no solution, output NIE. Otherwise, output TAK on the first line, and on the second line output $n$ positive integers, the sequence $a$ in order.

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

TAK
6 7 1000000000 6 3

3 2 1
2 3
3 5
1 3 1 2

NIE

2 1 1
1 1000000000
1 2 1 2

NIE

Hint

Original title: Pustynia.

Two additional sample tests are provided and can be downloaded from the attachments.

Translated by ChatGPT 5