Problem B
Majority Card
You are going to play a Majority^{1} Card game. In this game, there will be a deck of cards, initially empty. Each card is labelled with a number between $1$ to $2~ 000~ 000~ 000$ (or just between $1$ to $20$ on some occasions.) You will play the game in $N$ rounds, consecutively. For each round, one of these four possible scenarios can happen:

“PUT_TOP $X$ $Y$”: You put $X$ many cards labelled $Y$ at the top of the deck.

“PUT_BOTTOM $X$ $Y$”: You put $X$ many cards labelled $Y$ at the bottom of the deck.

“REMOVE_TOP $Z$”: You remove the $Z$ topmost cards.

“REMOVE_BOTTOM $Z$”: You remove the $Z$ bottommost cards.
After each round, you have to answer this question: “What is the majority card in the deck?” A majority card is a card label that appears the most in the deck and if tied, pick the smallest one. Can you help yourself by writing a program to play the Majority Card?
Input
The first line contains an integer, $N (1 \le N \le 200~ 000)$. The next $N$ lines contain the rounds, each on one line. Each round is given in one of four forms mentioned in above description where:

$1 \le X \le 10~ 000$,

$1 \le Y \le 2~ 000~ 000~ 000$, and

$1 \le Z \le C1$ where $C$ is the number of cards in the current deck (i.e. there will still be at least one card in the deck after each removal scenarios.)
Output
For each round, print the smallest majority card, separated by a newline.
Subtasks

($18$ Points): $N \le 2~ 000$, $X = 1$, $Y \le 20$.

($15$ Points): $X = 1$, $Y \le 20$.

($29$ Points): $Y \le 20$.

($6$ Points): The rounds are only PUT_TOP and PUT_BOTTOM.

($20$ Points): The rounds are only PUT_TOP and REMOVE_TOP.

($12$ Points): No additional constraint.
Warning
The I/O files are large. Please use fast I/O methods.
Explanation of Sample 1

After the $1$st round, the smallest majority card is $20$.

After the $2$nd round, the smallest majority card is $17$ (tied with $20$.)

After the $3$rd round, the smallest majority card is $8$ (tied with $17$ and $20$.)

After the $4$th round, the smallest majority card is $17$.

After the $5$th round, the smallest majority card is $17$ (tied with $20$.)

After the $6$th round, the smallest majority card is $20$.

After the $7$th round, the smallest majority card is $17$ (tied with $20$.)
Explanation of Sample 2

After the $1$st round, the smallest majority card is $2$.

After the $2$nd round, the smallest majority card is $7$.

After the $3$rd round, the smallest majority card is $7$.

After the $4$th round, the smallest majority card is $13$.

After the $5$th round, the smallest majority card is $7$ (tied with $13$.)

After the $6$th round, the smallest majority card is $2$ (tied with $13$.)

After the $7$th round, the smallest majority card is $13$.
Sample Input 1  Sample Output 1 

7 PUT_TOP 1 20 PUT_TOP 1 17 PUT_TOP 1 8 PUT_BOTTOM 1 17 PUT_BOTTOM 1 20 REMOVE_TOP 2 REMOVE_BOTTOM 1 
20 17 8 17 17 20 17 
Sample Input 2  Sample Output 2 

7 PUT_TOP 2 2 PUT_BOTTOM 4 7 PUT_TOP 3 13 PUT_BOTTOM 2 13 REMOVE_TOP 1 REMOVE_BOTTOM 5 REMOVE_BOTTOM 2 
2 7 7 13 7 2 13 
Footnotes
 The correct word should be “Plurality”, but many people are not familiar with this terminology.