Hide

# Problem BMajority Card

You are going to play a Majority1 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:

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

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

3. REMOVE_TOP $Z$”: You remove the $Z$ top-most cards.

4. REMOVE_BOTTOM $Z$”: You remove the $Z$ bottom-most 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 C-1$ 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.

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

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

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

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

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

6. ($12$ Points): No additional constraint.

## Warning

The I/O files are large. Please use fast I/O methods.

## Explanation of Sample 1

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

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

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

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

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

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

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

## Explanation of Sample 2

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

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

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

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

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

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

7. 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

1. The correct word should be “Plurality”, but many people are not familiar with this terminology.