Problem Description

Children love candies very much.

Now, Xiao K has some candies, each with a number representing its type.

There will be $q$ events, each involving adding a candy, removing a candy, or making an inquiry.

Each inquiry provides a $k$, indicating that Xiao K needs to distribute all the candies to $k$ children, and each child must receive at least one candy. Also, children do not like receiving the same candy. Specifically, when a child receives candy $i$, if they have already received candy $i$ before, their anger level increases by 1.

Xiao K does not like to see children angry, but Xiao K cannot solve this difficult problem, so you need to help Xiao K find a way to distribute the candies to minimize the sum of all children's anger levels.

It is guaranteed that there exists a distribution scheme such that each child receives at least one candy.

Each inquiry does not actually distribute candies, meaning the candies Xiao K has do not change after each inquiry.

Note that the process of distributing candies can be understood as dividing all the candies Xiao K has into $k$ non-empty sequences, which can be rearranged.

Input Format

The first line contains two positive integers $n, q$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, describing the candies Xiao K initially has.

The next $q$ lines, each containing two positive integers, describe an operation. There are three possible inputs:

1 x: Indicates that Xiao K has gained a candy of type $x$.

2 x: Indicates that Xiao K has lost a candy of type $x$, ensuring that Xiao K has at least one candy of type $x$ at this time.

3 k: Indicates that Xiao K needs to distribute the candies to $k$ children, and you need to find the minimum sum of all children's anger levels. Let $S$ represent the number of candies Xiao K has at this time, ensuring $1 \le k \le S$.

Output Format

For each inquiry, output a line containing an integer, representing the answer you found.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
2

Input Sample #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

Output Sample #2

1
5
6
7
1

Notes/Hints

【Sample Explanation 1】

During the first inquiry, Xiao K's candies are $\{3,5,2,5,5\}$, distributing to $2$ children as $\{2,3,5\},\{5,5\}$, with anger levels $0,1$. It can be proven that there is no scheme with a lower sum of anger levels.

【Data Range】

This problem uses subtask-bundled testing.

For $100\%$ of the data, $1 \le n, q \le 10^6$, $1 \le a_i, x \le n$. During each inquiry, let $S$ represent the number of candies Xiao K has, ensuring $1 \le k \le S$.

见题面 Input 部分

见题面 Output 部分