CF1097F Alex and a TV Show

Alex 决定试试自己的电视节目运气。他曾经参加过一个名为“What's That Word?!”的知识竞赛。在完美回答了“在互联网中，化名通常被称为什么？”（“呃……昵称？”）、“磁场强度的单位是以哪位著名发明家命名的？”（“呃……Nikola Tesla？”）以及“哪支摇滚乐队演唱了《How You Remind Me》？”（“呃……Nickelback？”）这些问题后，他决定报名参加一个更有难度的电视节目：“What's in This Multiset?!” 这个节目的规则如下：有 $n$ 个多重集，编号从 $1$ 到 $n$。每个多重集初始时都是空的。接下来会发生 $q$ 个事件，每个事件属于以下四种类型之一： - 1 x v —— 将第 $x$ 个多重集设置为只包含 $v$ 的单元素多重集 $\{v\}$。 - 2 x y z —— 将第 $x$ 个多重集设置为第 $y$ 个和第 $z$ 个多重集的并集。例如：$\{1, 3\} \cup \{1, 4, 4\} = \{1, 1, 3, 4, 4\}$。 - 3 x y z —— 将第 $x$ 个多重集设置为第 $y$ 个和第 $z$ 个多重集的积。两个多重集 $A$ 和 $B$ 的积 $A \times B$ 定义为 $\{\gcd(a, b) \mid a \in A,\, b \in B\}$，其中 $\gcd(p, q)$ 表示 $p$ 和 $q$ 的最大公约数。例如：$\{2, 2, 3\} \times \{1, 4, 6\} = \{1, 2, 2, 1, 2, 2, 1, 1, 3\}$。 - 4 x v —— 询问第 $x$ 个多重集中数字 $v$ 出现了多少次。由于之前的节目太难，现在参赛者只需要给出答案对 $2$ 取模后的结果即可。 注意，上述的 $x$、$y$ 和 $z$ 不一定互不相同。在第 $2$ 和第 $3$ 种事件中，先计算并集或积，然后再赋值。 Alex 被节目的复杂规则搞糊涂了。你能帮他回答所有第 $4$ 类事件的询问吗？

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 10^6$），分别表示多重集的数量和事件的数量。 接下来的 $q$ 行，每行描述一个事件，格式如题目描述所述。保证 $1 \leq x, y, z \leq n$ 且 $1 \leq v \leq 7000$ 恒成立。 保证至少有一个第 $4$ 类事件。

输出一个仅由数字 $0$ 和 $1$ 组成的字符串，长度等于第 $4$ 类事件的数量。第 $i$ 位表示第 $i$ 个第 $4$ 类事件的答案。

以下是示例测试中每次事件后多重集的状态；$i$ 表示已经处理的询问数量：  由 ChatGPT 4.1 翻译