在本题中，我们将考虑集合 $\{1, \dots, n\}$ 的 $n + m$ 个子集序列。集合 $A_1, \dots, A_n$ 定义如下：值 $1 \le i \le n$ 属于集合 $A_j$ 当且仅当 $i$ 能被 $j$ 整除。

例如，当 $n = 7$ 时，各集合如下： $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\}$

后续的 $m$ 个集合 $A_{n+1}, A_{n+2}, \dots, A_{n+m}$ 由对先前集合进行的并集、交集或补集运算产生。

• 集合 $A_i$ 与 $A_j$ 的并集运算（记作 $A_i \cup A_j$）生成的集合包含所有属于 $A_i$ 或 $A_j$ 的数字。
• 集合 $A_i$ 与 $A_j$ 的交集运算（记作 $A_i \cap A_j$）生成的集合包含所有同时属于 $A_i$ 和 $A_j$ 的数字。
• 集合 $A_i$ 的补集运算（记作 $A'_i$）生成的集合包含所有属于 $\{1, \dots, n\}$ 且不属于 $A_i$ 的整数。

操作序列示例如下： $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\}$

给定 $n, m$ 以及生成集合的操作列表，请回答 $q$ 个查询：给定的数字 $v$ 是否属于给定的集合 $A_x$。

输入格式

输入的第一行包含三个整数 $n, m, q$ ($1 \le n \le 50\,000, 1 \le m \le 400\,000, 1 \le q \le 1\,000\,000$)，分别表示初始集合的数量、操作数量以及查询数量。

接下来的 $m$ 行包含操作描述。第 $i$ 行描述了集合 $A_{n+i}$ 的生成方式，格式为以下三种之一： 1 x y：表示并集运算 $A_{n+i} = A_x \cup A_y$ 2 x y：表示交集运算 $A_{n+i} = A_x \cap A_y$ * 3 x：表示补集运算 $A_{n+i} = A'_x$

在每种格式中，值 $x, y$ 满足 $1 \le x, y < n + i$，即每个操作仅引用之前的集合。

接下来的 $q$ 行包含查询。每行包含两个整数 $x$ 和 $v$ ($1 \le x \le n + m, 1 \le v \le n$)，表示询问 $v \in A_x$ 是否成立。

输出格式

输出 $q$ 行，包含对各查询的回答。每行应包含单词 TAK 或 NIE。TAK 表示 $v \in A_x$，NIE 表示 $v \notin A_x$。

样例

输入 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

输出 1

TAK
NIE
NIE
TAK
TAK
NIE
TAK
NIE
TAK

说明 1

测试样例对应于题目描述中给出的操作示例。