Most frequent value - MarisaOJ: Marisa Online Judge

Most frequent value

Time limit: 1000 ms
Memory limit: 256 MB
Given an initially empty set $S$, there are $q$ queries, each of the following format: - `1 x a`: Insert $a$ elements of value $x$ into the set. - `2 x b`: Remove $b$ elements of value $x$ from the set. If the number of elements with value $x$ in the set is less than $b$, remove all elements with value $x$. - `3`: Print the value with the highest frequency in $S$. In case of a tie, print the maximum value. It is guaranteed that the set $S$ contains at least one element at this point. The set $S$ can contain multiple elements with the same value. ### Input - The first line contains an integer $q$. - The next $q$ lines, each line contains a query in the specified format. ### Output - For each query of type $3$, print an integer as the answer. ### Constraints - $1 \le q \le 10^5$. - $1 \le x,a,b \le 10^9$. ### Sample test Input ``` 8 1 1 3 1 2 2 3 1 2 1 3 1 5 10 2 5 7 3 ``` Output: ``` 1 2 5 ```