4396: C维护集合(set)

内存限制:512 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:8 解决:2

题目描述

### C维护集合(set) 小 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

提示

### 样例一 #### 输入 ``` 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$ 。 | 测试点 | $n\le$ | $q\le$ | $x\le$ | $a_i,t\le $ | 特殊性质 | | ----------- | ------ | ------ | ------ | ----------- | ---------- | | $1\sim 4$ | $10$ | $10$ | $10$ | $10$ | 无 | | $5\sim 10$ | $10^3$ | $10^3$ | $10^3$ | $10^3$ | 无 | | $11\sim 12$ | 无限制 | $10^3$ | 无限制 | $10^3$ | 无 | | $13\sim 14$ | 无限制 | 无限制 | $300$ | 无限制 | 无 | | $15\sim 16$ | 无限制 | 无限制 | 无限制 | 无限制 | $\text{A}$ | | $17\sim 20$ | 无限制 | 无限制 | 无限制 | 无限制 | 无 | $\text{A}:$ 保证没有操作 $1,2$ 。