题目描述

在这道题中，我们考虑一个由 $n+m$ 个集合组成的序列，这些集合都是 $\{1, \ldots, n\}$ 的子集。前 $n$ 个集合 $A_{1}, \ldots, A_{n}$ 的定义如下：对于 $1 \leq i \leq n$，数字 $i$ 属于集合 $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}, \ldots, A_{n+m}$ 通过对已有集合进行并集、交集或补集运算生成：

• 并集 $A_{i} \cup A_{j}$：包含所有属于 $A_{i}$ 或 $A_{j}$ 的数字；
• 交集 $A_{i} \cap A_{j}$：包含所有同时属于 $A_{i}$ 和 $A_{j}$ 的数字；
• 补集 $A_{i}^{\prime}$：包含 $\{1, \ldots, n\}$ 中不属于 $A_{i}$ 的所有数字。

例如，一组可能的运算序列可能是：

• $A_{8}=A_{5} \cup A_{7}=\{5,7\}$
• $A_{9}=A_{2} \cap A_{3}=\{6\}$
• $A_{10}=A_{8}^{\prime}=\{1,2,3,4,6\}$
• $A_{11}=A_{10} \cap A_{8}=\{\}$
• $A_{12}=A_{3}^{\prime}=\{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 \leq n \leq 50000, 1 \leq m \leq 400000, 1 \leq q \leq 1000000)$，分别表示初始集合数量、运算次数和询问次数。

接下来的 $m$ 行描述运算，每行对应生成集合 $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}^{\prime}$。
  其中，$x, y$ 满足 $1 \leq x, y < n+i$，即运算只引用之前的集合。

接下来的 $q$ 行描述询问，每行包含两个整数 $x$ 和 $v$ $(1 \leq x \leq n+m, 1 \leq v \leq n)$，询问 $v$ 是否属于 $A_{x}$。

输出格式

输出 $q$ 行，每行回答一个询问，用 TAK 或 NIE 表示。TAK 表示 $v \in A_{x}$，NIE 表示 $v \notin A_{x}$。

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

TAK
NIE
NIE
TAK
TAK
NIE
TAK
NIE
TAK

此样例对应题目描述中给出的运算序列，结果与上述集合定义一致。