小 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 是操作三的个数。

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

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