该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近学了一个新知识——幂约数，跟往常的约数性质一样

如果一个数字 $A$ 的 $y$ 次方可以被 $x$ 整除（即满足 $x \% A^y == 0$），则称 $A$ 是 $x$ 的 $y$ 次幂约数

借着这个知识点，徐老师想出一个数据结构相关的题目

现在你需要维护一个数字序列，一开始这个数字序列有 $n$ 个整数,依次为 $a_1 \sim a_n$

接下来徐老师会给出三种不同的操作：

• 1 x：删除现在序列中的一个整数 $x$（保证删除时序列中至少存在一个 $x$）
• 2 x：在现有的数字序列末尾增加一个整数 $x$
• 3 x：求最大的 $y$，使得当前序列中存在一个整数 $a_i$ 是 $x$ 的 $y$ 次幂约数

现在徐老师请你来尝试完成这个数据结构的维护。

输入格式

第 $1$ 行包含两个正整数 $n,m$，表示初始数字序列中的数字个数和操作次数。

第 $2$ 行包含 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示初始数字序列中的数字。

接下来 $m$ 行，每行表示一个操作，操作的输入格式如题意所示。

输出格式

输出一共 $m$ 行，对于每次询问输出一个答案

数据范围

特别的，保证所有数据满足：

• $1 \leq n,m,a_i,x \leq 10^5$

• $a_i \neq 1$ 且操作 $1,2$ 的 $x$ 均 $\neq 1$

样例输入

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

样例输出

2
1
1
1
0

样例解释

第一次询问 $9$，此时序列中的 $3$ 是 $9$ 的 $2$ 次幂约数 第二次询问 $6$，此时序列中的 $3$ 和 $6$ 都是 $6$ 的 $1$ 次幂约数 第三次询问 $6$，此时序列中的 $3$ 是 $6$ 的 $1$ 次幂约数 第四次询问 $5$，此时序列中的 $3,4,7$ 都可以是 $5$ 的 $0$ 次幂约数