Desert

The route from Bythad to Bytara crosses the sands of the Great Byteotian Desert. The trip is hard, especially because there are only $s$ wells along the route. Knowing that the prosperity of his country depends on its communication routes, the ruler of Byteotia has decided to have new wells dug along this route. The distance from Bythad to Bytara is $n+1$ bytemiles. At each integer multiple of a bytemile from Bythad, there is already a well, or a new one can be dug. The lower the water level is, the harder and more costly it is to dig a well.

The royal geologist Byteasar surveys the options. He has $m$ measurements from the satellite network. The satellite data do not give the water levels directly. Each measurement covers a contiguous fragment of the route and says only that, at certain points of that fragment, the water level is lower than at the remaining points. The water level at every point is between 1 and $10^9$ bytemeters below the surface. Help Byteasar find a possible water level at every point along the route. The satellite data may be contradictory.

The first line contains three integers $n$, $s$, and $m$ separated by single spaces ($1 \le s \le n \le 100\,000$, $1 \le m \le 200\,000$), where $n$ is the number of wells, $s$ is the number of wells already dug, and $m$ is the number of satellite measurements.

Each of the next $s$ lines contains two integers $p_i$ and $d_i$ ($1 \le p_i \le n$, $1 \le d_i \le 10^9$). Well $i$ is $p_i$ bytemiles from Bythad, and the water level in it is $d_i$ bytemeters below the surface. The wells are given in increasing order of $p_i$.

Each of the next $m$ lines contains integers $l_i$, $r_i$, $k_i$, followed by $k_i$ integers $x_1, \ldots, x_{k_i}$ ($1 \le l_i < r_i \le n$, $1 \le k_i \le r_i - l_i$, $l_i \le x_1 < \cdots < x_{k_i} \le r_i$). The measurement says that the water level at each of the points $x_1, \ldots, x_{k_i}$ is strictly lower than the water level at each of the remaining integer points in $\{l_i, \ldots, r_i\} \setminus \{x_1, \ldots, x_{k_i}\}$. The sum of all $k_i$ does not exceed $200\,000$.

Tests worth 60% of the score satisfy $n, m \le 1000$. Tests worth 30% of the score have a sum of $k_i$ at most $1000$.

If the measurements are contradictory, print NIE on the first line. Otherwise, print TAK on the first line and, on the second line, print $n$ integers from 1 to $10^9$: the water levels at the successive points along the route from Bythad. If several solutions exist, print any one of them.