Reimu has n flowers, and the color of the $i$-th flower is $a_i$. Over the next $q$ days, the following events may occur:
- `1 x`: Reimu receives an additional flower of color $x$.
- `2 x`: A flower of color $x$ withers.
- `3 k`: Reimu wants to try placing all of her flowers into $k$ vases, with each vase receiving at least one flower. When placing a flower into a vase, if there is already a flower of the same color in that vase, the "ugliness" of that vase increases by one. Reimu wants to know the minimum possible total ugliness that can be achieved. It is guaranteed that there is always at least one valid way to arrange the flowers.
After placing the flowers, Reimu takes them out, so the total number of flowers remains unchanged after each event of type `3`.
Input:
- The first line contains two integers $n$ and $q$.
- The second line contains $n$ integers $a_i$.
- The next $q$ lines each contain an event.
Output:
- For each event of type `3`, output the minimum possible total ugliness.
Constraints:
- $1 ≤ n, q ≤ 10^6$.
- $1 ≤ a_i, x ≤ n$.
Example
Input:
```
5 4
3 5 2 5 5
3 2
2 5
1 5
3 1
```
Output:
```
1
2
```
