【MX-S1-T2】催化剂

小朋友们很喜欢糖果。 现在，小 K 有一些糖果，每个糖果上有一个数字代表它的种类。 有 $q$ 次事件，每次事件会加入一个糖果、或删除一个糖果、或提出一次询问。 每次询问会给出一个 $k$，表示小 K 现在需要将所有糖果分给 $k$ 个小朋友，并且每个小朋友都需要得到至少一个糖果。同时，小朋友们不喜欢得到相同的糖果。具体的，在一个小朋友得到了糖果 $i$ 时，如果 Ta 在这个糖果之前就已经获得过糖果 $i$，那么 Ta 就会感到非常生气，Ta 的愤怒值就会增加 $1$。 小 K 不喜欢看到小朋友们生气，但小 K 无法解决这么困难的问题，所以你需要帮小 K 求出一种分糖果的方式，最小化所有小朋友的愤怒值之和。 保证存在一种分糖果的方案，使得每个小朋友都分到至少一个糖果。 每次询问并没有真正的分糖果，即每次询问后小 K 拥有的糖果不会改变。 注意，分糖果的过程可以理解为将小 K 拥有的所有糖果划分到 $k$ 个非空序列，可以重排。

第一行两个正整数 $n,q$。 第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，描述初始时小 K 拥有的糖果。 接下来 $q$ 行，每行两个正整数，描述一次操作，共有三种可能的输入： `1 x`：表示小 K 又拥有了一个种类为 $x$ 的糖果。 `2 x`：表示小 K 丢失了一个种类为 $x$ 的糖果，保证此时小 K 拥有至少一个种类为 $x$ 的糖果。 `3 k`：表示此时小 K 需要把糖果分给 $k$ 个小朋友，你需要求出最小的所有小朋友的愤怒值之和。令 $S$ 表示此时小 K 拥有的糖果数量，保证 $1\le k\le S$。

对于每次询问，输出一行一个整数，表示你求出的答案。

5 4
3 5 2 5 5
3 2
2 5
1 5
3 1

1
2

5 15
2 5 2 5 1
2 1
1 1
1 2
1 4
1 1
3 2
1 1
3 1
1 5
3 1
1 2
3 1
2 1
3 3
2 2

1
5
6
7
1

__【样例解释 1】__ 第一次询问时，小 K 手上的糖果为 $\{3,5,2,5,5\}$，分给 $2$ 个小朋友的糖果为 $\{2,3,5\},\{5,5\}$，小朋友的愤怒值为 $0,1$。可以证明没有愤怒值之和更小的方案。 __【数据范围】__ __本题使用子任务捆绑测试。__ 对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$1\le a_i,x\le n$。每次询问时，令 $S$ 表示此时小 K 拥有的糖果数量，保证 $1\le k\le S$。 | 子任务编号 | $n\le $ | $q\le $ | 特殊性质 | 分值 | | ---------- | ------- | ------- | ------------- | ---- | | $1$ | $5$ | $15$ | 无 | $20$ | | $2$ | $2000$ | $2000$ | 无 | $20$ | | $3$ | $10^5$ | $10^5$ | 无 | $20$ | | $4$ | $10^6$ | $10^6$ | $a_i,x\le 50$ | $10$ | | $5$ | $10^6$ | $10^6$ | $k\le 50$ | $10$ | | $6$ | $10^6$ | $10^6$ | 无 | $20$ |