In this task, we consider a sequence of $n + m$ subsets of the set $\{1, \dots, n\}$. The sets $A_1, \dots, A_n$ are defined as follows: a value $1 \le i \le n$ belongs to the set $A_j$ if and only if $i$ is divisible by $j$.

For example, for $n = 7$, the initial sets are: $A_1 = \{1, 2, 3, 4, 5, 6, 7\}$ $A_2 = \{2, 4, 6\}$ $A_3 = \{3, 6\}$ $A_4 = \{4\}$ $A_5 = \{5\}$ $A_6 = \{6\}$ * $A_7 = \{7\}$

The subsequent $m$ sets — $A_{n+1}, A_{n+2}, \dots, A_{n+m}$ — are created by union, intersection, or negation operations on previous sets. The union operation of sets $A_i$ and $A_j$ (denoted by $A_i \cup A_j$) creates a set containing all numbers belonging to either $A_i$ or $A_j$. The intersection operation of sets $A_i$ and $A_j$ (denoted by $A_i \cap A_j$) creates a set containing all numbers belonging to both $A_i$ and $A_j$. * The negation operation of set $A_i$ (denoted by $A'_i$) creates a set containing all integers $1 \le j \le n$ that do not belong to $A_i$.

An example sequence of operations might look as follows: $A_8 = A_5 \cup A_7 = \{5, 7\}$ $A_9 = A_2 \cap A_3 = \{6\}$ $A_{10} = A'_8 = \{1, 2, 3, 4, 6\}$ $A_{11} = A_{10} \cap A_8 = \{\}$ $A_{12} = A'_3 = \{1, 2, 4, 5, 7\}$ $A_{13} = A_{12} \cup A_{12} = \{1, 2, 4, 5, 7\}$ $A_{14} = A_{10} \cap A_{13} = \{1, 2, 4\}$ $A_{15} = A_9 \cup A_{14} = \{1, 2, 4, 6\}$

Given $n, m$, and the list of operations creating the sets, answer $q$ queries of the form: does a given number $v$ belong to a given set $A_x$?

Input

The first line of the input contains three integers $n, m, q$ ($1 \le n \le 50\,000$, $1 \le m \le 400\,000$, $1 \le q \le 1\,000\,000$), representing the number of initial sets, the number of operations, and the number of queries, respectively.

The next $m$ lines contain descriptions of the operations. The $i$-th line, describing how the set $A_{n+i}$ was formed, is in one of three forms: 1 x y – representing the union operation $A_{n+i} = A_x \cup A_y$, 2 x y – representing the intersection operation $A_{n+i} = A_x \cap A_y$, * 3 x – representing the negation operation $A_{n+i} = A'_x$.

In each of these forms, the values $x, y$ satisfy the condition $1 \le x, y < n + i$, i.e., each operation refers only to previous sets.

The next $q$ lines contain queries. Each contains two integers $x$ and $v$ ($1 \le x \le n + m$, $1 \le v \le n$), which represent a query about whether $v \in A_x$.

Output

Output $q$ lines containing the answers to the consecutive queries. Each line should contain one of the words TAK or NIE. The word TAK means that $v \in A_x$ for the corresponding $x, v$, while the word NIE means that $v \notin A_x$.

Examples

Input 1

7 8 9
1 5 7
2 2 3
3 8
2 10 8
3 3
1 12 12
2 10 13
1 9 14
2 4
5 7
11 5
15 1
15 2
15 3
15 4
15 5
15 6

Output 1

TAK
NIE
NIE
TAK
TAK
NIE
TAK
NIE
TAK

Note

The example test corresponds to the example operations described in the problem statement.