P3588 [POI 2015 R2] Desert

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.

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$.)

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.

Original title: Pustynia. Two additional sample tests are provided and can be downloaded from the attachments. Translated by ChatGPT 5