{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eThe memory limit of this problem (8 megabytes) is unusual!\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAlice 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\u0027t 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.\u003c/p\u003e\u003cp\u003eThey 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.\u003c/p\u003e\u003cp\u003eOn each day, one of the following two events will happen: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eADD a[i] b[i]\u003c/span\u003e\" ($$$1\\leq a[i]\u0026lt;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. \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eDEL\u003c/span\u003e\" : Alice removes the rightmost pile. It is guaranteed that such pile always exists. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYou 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains only a single case.\u003c/p\u003e\u003cp\u003eThe first line of the input contains a single integer $$$n$$$ ($$$1 \\leq n \\leq 40\\,000$$$), denoting the number of days.\u003c/p\u003e\u003cp\u003eEach of the next $$$n$$$ lines describes an event, the $$$i$$$-th of which denotes the event happened on the $$$i$$$-th day.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the number of \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eADD\u003c/span\u003e\" events will never exceed $$$20\\,000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$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.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\nADD 3 10\nADD 2 4\nADD 1 5\nADD 2 1\nDEL\nDEL\nADD 3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n14\n0\n1\n0\n14\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}