题目描述

小 A 最近学习了数论的相关知识，若 $a$ 是 $b$ 的约数，则 $b$ 能够被 $a$ 整除，即 $b\bmod a=0$ 。

学习之后，他发现自己很喜欢约数，便定义了 $c$ 重约数。若 $a$ 是 $b$ 的 $c$ 重约数，则 $b$ 能够被 $a^c$ 整除，即 $b\bmod a^c=0$ 。

之后小 A 思考了这样一个问题：小 A 需要维护一个初始大小为 $n$ 的集合 $a$ 。小 A 需要支持在集合 $a$ 上的 $Q$ 次操作，操作共三种，参数分别如下：

• 1 t删除集合中的一个元素 $t$ ，保证该元素 $t$ 在集合中存在。
• 2 t往集合中加入一个元素 $t$ 。
• 3 x求出最大的 $k$ ，使得集合中存在一个数 $y$，是 $x$ 的 $k$ 重约数。(注：$k$ 是可以为 $0$ 的)

但小 A 并不会做，所以他来请你回答这个问题。

输入格式

第 $1$ 行包含两个正整数 $n,Q$，表示初始集合大小，操作次数。

第 $2$ 行包含 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示初始集合。

随后 $n$ 行，每行描述一次操作，见题意。保证数据合法。

输出格式

包含 $q$ 行，其中 $q$ 是操作三的个数。

5 8
4 4 6 2 7 
2 3
3 9
1 2
3 6
1 4
3 3
1 6
3 6

2
1
1
1

数据范围

对于所有数据 $n,q,a_i,x,t\le 10^5,a_i,t\neq1$ 。

$\text{A}:$ 保证没有操作 $1,2$ 。