Problem Description

You need to maintain a sequence that supports $4$ types of operations:

1. 1 x y: Insert $y$ numbers $x$ into the sequence consecutively.
2. 2 x y: Delete $x$ from the sequence $y$ times consecutively. If, in some deletion, $x$ no longer exists in the sequence, ignore that deletion.
3. 3: Deduplicate the sequence. That is, for each distinct positive integer $x$ that has appeared in the sequence, if it appears more than $1$ time, keep only one $x$ in the sequence and delete all the others.
4. 4 x: Query the number of occurrences of $x$ in the sequence.

For each operation 4, output the answer.

Input Format

The first line contains an integer $q$, which represents the number of operations.

The next $q$ lines each contain several integers, describing one operation.

Output Format

For each operation 4, output one line containing the answer.

The testdata guarantees that there is at least one operation 4.

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

5
1

4
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
4 1000000000

3000000000

20
4 95002957
2 384405322 255642125
2 384405322 174926753
2 384405322 51265222
1 384405322 311383201
4 384405322
1 384405322 5464229
4 22438767
4 17075617
1 384405322 153189933
1 230228188 148299369
1 7168162 387115701
1 384405322 154480360
1 384405322 438458686
3
1 7961090 98996809
4 153074129
1 975025351 171484003
1 384405322 650527951
4 384405322

0
311383201
0
0
0
650527952

Hint

Sample Explanation $1$

Operation $1$: Insert $10$ copies of $2$.

Operation $2$: Delete $5$ copies of $2$. After that, the sequence contains only $5$ copies of $2$.

Operation $3$: Query the number of occurrences of $2$, which is $5$.

Operation $4$: Deduplicate the sequence. After that, the sequence contains only one $2$.

Operation $5$: Query the number of occurrences of $2$, which is $1$.

Sample Explanation $2$

Please note that the answer may exceed the range of int.

Constraints

For $100\%$ of the testdata, $1 \le q \le 10^5$, $1 \le x, y \le 10^9$.

Please note: Since there is no partial scoring in the contest where this problem comes from, you can get full score only by passing all test points; otherwise, you will get $0$ points.

Translated by ChatGPT 5