Problem Description

Given a sequence \( a \) of length \( n \) consisting of positive integers, each number ranging from \( 1 \) to \( 10^9 \). You are informed of \( s \) specific numbers in the sequence and provided with \( m \) pieces of information. Each piece of information contains three numbers \( l, r, k \) followed by \( k \) positive integers, indicating that any of the \( k \) numbers among \( a_l, a_{l+1}, \ldots, a_{r-1}, a_r \) is strictly greater than any of the remaining \( r-l+1-k \) numbers.

Construct a solution that satisfies these conditions, or determine if no solution exists.

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 \), indicating that \( a_{p_i} = d_i \), with \( p_i \) being strictly increasing.

The following \( m \) lines each start 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 < \ldots < x_{k_i} \leq r_i \)), indicating that any of these \( k_i \) numbers is strictly greater than any of the remaining \( r_i-l_i+1-k_i \) numbers (\( \sum k \leq 3 \times 10^5 \)).

Output Format

If no solution exists, output NIE. Otherwise, output TAK on the first line, followed by \( n \) positive integers on the second line, representing each number in the sequence \( a \).

Sample Input and Output

Sample Input #1

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

Sample Output #1

TAK
6 7 1000000000 6 3

Sample Input #2

3 2 1
2 3
3 5
1 3 1 2

Sample Output #2

NIE

Sample Input #3

2 1 1
1 1000000000
1 2 1 2

Sample Output #3

NIE

Notes

The original problem name is "Pustynia."

Additional sample cases are available for download in the attachments.

见题面 Input 部分

见题面 Output 部分