题目描述

小朋友们很喜欢糖果。

现在，小 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$。