题目背景

小A最近沉浸在数论的奇妙世界中，他对“约数”这个概念情有独钟，甚至还脑洞大开定义了一个全新的概念——“c重约数”。现在，他带着一个关于集合维护与查询的问题来向你求助啦！

题目描述

我们都知道，若 $a$ 是 $b$ 的约数，则 $b$ 能够被 $a$ 整除，即 $b \bmod a = 0$。

小A在此基础上定义了c重约数：若 $a$ 是 $b$ 的 $c$ 重约数，则 $b$ 能够被 $a^c$ 整除，即 $b \bmod a^c = 0$。

现在，小A需要维护一个初始大小为 $n$ 的集合 $a$，并支持 $Q$ 次操作，操作共分为以下三种：

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

请你帮小A处理这些操作吧！

输入格式

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

第 2 行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示初始集合中的元素。

随后 $Q$ 行，每行描述一次操作，格式如题目描述所述。保证数据合法。

输出格式

输出共 $q$ 行，其中 $q$ 是操作 3 的个数。每行一个整数，表示对应操作 3 的答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
1
1

数据范围与提示

对于所有数据，保证：

• $1 \le n, Q, a_i, x, t \le 10^5$
• $a_i, t \neq 1$

特殊性质 A：保证没有操作 1 和操作 2（即集合始终不变）。