← 返回题目列表

Codeforces · 1097/F

F. 亚历克斯和电视节目

中文机器翻译题面 查看原题

亚历克斯决定在电视节目中碰碰运气。他曾经参加过一个名为“那个词是什么?!”的测验。在完美回答了“网络上通常如何称呼笔名?”的问题后。 (“嗯......一个缺口?”),“我们以哪位著名发明家的名字命名磁场强度的单位?” (“嗯......尼古拉特斯拉?”)和“哪个摇滚乐队表演“How You Remind Me”? (“嗯……五分钱?”),他决定申请一个更难一点的电视节目:“This Multiset 里有什么?!”。

该电视节目的规则如下:有 $$$n$$$ 多重集,编号从 $$$1$$$ 到 $$$n$$$。它们每个最初都是空的。然后,$$$q$$$事件发生;它们中的每一个都属于四种可能类型之一:

- 1 x v — 将第 $$$x$$$ 个多重集设置为单例 $$$\{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$$$ 类型的事件中,首先计算总和或乘积,然后执行赋值。

亚历克斯对节目复杂的规则感到困惑。你能帮助他回答$$$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$$$ 位数字应等于第 $$$4$$$ 类型的第 $$$i$$$ 查询的答案。

示例

输入 #1

4 13
1 1 1
1 2 4
1 3 6
4 4 4
1 4 4
2 2 1 2
2 3 3 4
4 4 4
3 2 2 3
4 2 1
4 2 2
4 2 3
4 2 4

输出 #1

010101

注意

以下是在每个事件之后的示例测试中多重集的外观; $$$i$$$ 是迄今为止处理的查询数量: