小朋友们很喜欢糖果。
现在，小 K 有一些糖果，每个糖果上有一个数字代表它的种类。
有 $q$ 次事件，每次事件会加入一个糖果、或删除一个糖果、或提出一次询问。
每次询问会给出一个 $k$，表示小 K 现在需要将所有糖果分给 $k$ 个小朋友，并且每个小朋友都需要得到至少一个糖果。同时，小朋友们不喜欢得到相同的糖果。具体的，在一个小朋友得到了糖果 $i$ 时，如果 Ta 在这个糖果之前就已经获得过糖果 $i$，那么 Ta 就会感到非常生气，Ta 的愤怒值就会增加 $1$。
小 K 不喜欢看到小朋友们生气，但小 K 无法解决这么困难的问题，所以你需要帮小 K 求出一种分糖果的方式，最小化所有小朋友的愤怒值之和。
保证存在一种分糖果的方案，使得每个小朋友都分到至少一个糖果。
每次询问并没有真正的分糖果，即每次询问后小 K 拥有的糖果不会改变。
注意，分糖果的过程可以理解为将小 K 拥有的所有糖果划分到 $k$ 个非空序列，可以重排。
## Input
第一行两个正整数 $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$。
## Output
对于每次询问，输出一行一个整数，表示你求出的答案。
[samples]
## Background
原题链接：<https://oier.team/problems/S1B>。
## Note
__【样例解释 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$ |