사막

Bythad에서 Bytara까지 가는 길은 Great Byteotian Desert의 모래 사이를 지난다. 이 길은 여행하기 힘들고, 특히 길을 따라 있는 우물이 $s$개뿐이라서 더 그렇다. 나라의 번영이 교통로에 달려 있다는 것을 아는 Byteotia의 통치자는 이 길을 따라 새 우물을 파기로 했다. Bythad에서 Bytara까지의 거리는 $n+1$ bytemile이다. Bythad에서 bytemile의 정수 배 지점마다 이미 우물이 있거나, 새로 팔 수 있다. 수위가 낮을수록 우물을 파기 어렵고 비용도 많이 든다.

왕실 지질학자 Byteasar가 후보지를 조사한다. 그는 위성 네트워크로 얻은 측정값 $m$개를 가지고 있다. 위성 자료는 수위를 직접 알려주지 않는다. 각 측정값은 길의 연속된 구간을 다루며, 그 구간의 특정 지점들의 수위가 나머지 지점들보다 낮다는 사실만 알려준다. 모든 지점의 수위는 지표면 아래 1 bytemeter 이상 $10^9$ bytemeter 이하이다. Byteasar를 도와 길을 따라 각 지점의 수위가 얼마일 수 있는지 구하라. 위성 자료가 서로 모순될 수도 있다.

첫 줄에는 공백으로 구분된 정수 세 개 $n$, $s$, $m$이 주어진다 ($1 \le s \le n \le 100\,000$, $1 \le m \le 200\,000$). $n$은 우물의 개수, $s$는 이미 있는 우물의 개수, $m$은 위성 측정의 개수이다.

다음 $s$개 줄에는 정수 $p_i$, $d_i$가 주어진다 ($1 \le p_i \le n$, $1 \le d_i \le 10^9$). 우물 $i$는 Bythad에서 $p_i$ bytemile 떨어져 있고, 그 수위는 지표면 아래 $d_i$ bytemeter이다. 우물은 $p_i$가 증가하는 순서로 주어진다.

다음 $m$개 줄에는 정수 $l_i$, $r_i$, $k_i$와 이어서 정수 $k_i$개 $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$). 이 측정은 $x_1, \ldots, x_{k_i}$ 지점의 수위가 $\{l_i, \ldots, r_i\} \setminus \{x_1, \ldots, x_{k_i}\}$에 속한 나머지 정수 지점의 수위보다 엄격히 낮다는 뜻이다. 모든 $k_i$의 합은 $200\,000$을 넘지 않는다.

전체 점수의 60%에 해당하는 테스트에서는 $n, m \le 1000$이다. 30%에 해당하는 테스트에서는 $k_i$의 합이 $1000$ 이하이다.

측정값이 모순되면 첫 줄에 NIE를 출력한다. 그렇지 않으면 첫 줄에 TAK를 출력하고, 둘째 줄에 Bythad에서 차례대로 있는 각 지점의 수위를 1 이상 $10^9$ 이하인 정수 $n$개로 출력한다. 해가 여러 개이면 그중 아무거나 하나를 출력한다.