{"trustable":false,"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\"\u003e注意空间限制为 8MB\u003c/span\u003e\u003c/p\u003e\n\u003cp\u003eAlice 和 Bob 正在玩 Nim 游戏,在这个游戏中,有几堆石头,每堆可能包含多块石头,两名玩家轮流移除石头,在每次移动中,玩家可以选择一堆石头,然后从中取出正整数的石头,不能移除石头的玩家先输.\u003c/p\u003e\n\u003cp\u003e在接下来的 $$$n$$$ 天他们会进行 $$$n$$$ 轮游戏, 每天进行一轮. 最初,没有成堆的石头. 在第 $$$i$$$ 天, 恰好会发生一个事件, 然后他们将进行新的游戏. Alice 先采取行动, 并且两个玩家都足够聪明. 但是 Bob 想通过作弊来取胜. 在每轮游戏开始前, Bob 可以付出一些代价来删除某些石头堆, 这样 Alice 就永远都赢不了. 在每轮游戏结束后, Bob 会还原已删除的石头堆.\u003c/p\u003e\n\u003cp\u003e每天, 将发生以下两个事件之一: \u003c/p\u003e\n\u003cul\u003e \n \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 把包含 $$$a[i]$$$ 个石头的石头堆添加到所有石头堆的右边, 该石头堆需要 Bob 花费 $$$b[i]$$$ 的代价去删除. \u003c/li\u003e\n \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eDEL\u003c/span\u003e\" : Alice 移除掉最右边的石头堆. 保证这样的石头堆存在. \u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e你是 Bob 最好的朋友,请帮助 Bob 确定每局游戏要删除哪些石头堆,从而使作弊的代价最小化,请注意,鲍勃总是可以通过删除所有石头堆来获胜.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e输入只包含一组测试.\u003c/p\u003e\n\u003cp\u003e第一行包含一个整数 $$$n$$$ ($$$1 \\leq n \\leq 40\\,000$$$), 表示游戏的天数.\u003c/p\u003e\n\u003cp\u003e接下来 $$$n$$$ 行每行描述了一个事件, 其中第 $$$i$$$ 行表示事件发生在第 $$$i$$$ 天.\u003c/p\u003e\n\u003cp\u003e保证 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eADD\u003c/span\u003e\" 事件的总和不会超过 $$$20\\,000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出 $$$n$$$ 行, 第 $$$k$$$ $$$(1\\le k \\le n)$$$ 行包含一个整数, 表示 Bob 在第 $$$k$$$ 天需要付出的最小代价.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e7\nADD 3 10\nADD 2 4\nADD 1 5\nADD 2 1\nDEL\nDEL\nADD 3 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e10\n14\n0\n1\n0\n14\n4\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}