题目背景

PA 2025 trial round t1.

由于评测机性能差距，微调了 TL 和 ML。

请注意本题非同寻常的时空限制。

题目描述

给定正整数 $n,m$。定义全集 $U=\{1,2,\ldots,n\}$。

构造 $(n+m)$ 个集合 $A_1,A_2,\ldots,A_{n+m}$：

1. 对于 $1\le i\le n$，$A_i$ 里的元素为 $U$ 中 $i$ 的倍数。

2. 对于 $n+1\le i\le m$，给定参数 $op_i$：

   • 当 $op_i=1$ 时，给定参数 $x,y$，则 $A_{i}=A_x\cup A_y$；
   • 当 $op_i=2$ 时，给定参数 $x,y$，则 $A_{i}=A_x\cap A_y$；
   • 当 $op_i=3$ 时，给定参数 $x$，则 $A_{i}=U\backslash A_x$（即 $A_i=\{j:j\in U,j\not\in A_x\}$）。

接着有 $q$ 次询问，每次询问给定两个正整数 $x,y$，问是否有 $y\in 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

提示

• $1\le n\le 5\times 10^4$；
• $1\le m\le 4\times 10^5$；
• $1\le q\le 10^6$。