408452: GYM103119 I Nim Cheater

The memory limit of this problem (8 megabytes) is unusual!

Alice and Bob are playing the Nim game. In this game, there are several piles of stones, where each pile may contain multiple stones. Two players take turns to remove stones. The player who can't take any legal move first loses. In each move, the player can select a pile of stones, then remove a positive number of stones from it.

They will play $$$n$$$ games in the next $$$n$$$ days, one game per day. Initially, there are no piles of stones. On the $$$i$$$-th day, exactly one event will happen, and then they will play a new game. Alice always takes moves first, and both of the players will play optimally. Bob wants to win the game by cheating. Before each game, Bob can pay to delete several piles of stones such that Alice can never win. And after each game, Bob will restore all the deleted piles back.

On each day, one of the following two events will happen:

• "ADD a[i] b[i]" ($$$1\leq a[i]<16\,384$$$, $$$1\leq b[i]\leq 100\,000$$$): Alice puts a new pile of $$$a[i]$$$ stones as the rightmost pile, which will cost Bob $$$b[i]$$$ dollars to delete it.
• "DEL" : Alice removes the rightmost pile. It is guaranteed that such pile always exists.

You are the best friend of Bob, please help Bob determine which piles of stones to delete for each game such that the total cheating cost is minimized. Note that Bob can always win by deleting all the piles.

The input contains only a single case.

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 40\,000$$$), denoting the number of days.

Each of the next $$$n$$$ lines describes an event, the $$$i$$$-th of which denotes the event happened on the $$$i$$$-th day.

It is guaranteed that the number of "ADD" events will never exceed $$$20\,000$$$.

Print $$$n$$$ lines, where the $$$k$$$-th $$$(1\le k \le n)$$$ line contains a single integer, the minimum number of dollars that Bob needs to pay on the $$$k$$$-th day.

7
ADD 3 10
ADD 2 4
ADD 1 5
ADD 2 1
DEL
DEL
ADD 3 5

10
14
0
1
0
14
4