坡旅甲(再次)玩电脑游戏。在这款游戏中,他使用魔法咒语与怪物战斗。
法术有两种类型:力量之火法术 $$$x$$$ 对怪物造成 $$$x$$$ 伤害,力量闪电法术 $$$y$$$ 对怪物造成 $$$y$$$ 伤害,并使波利卡普施放的下一个法术伤害加倍。每个法术在每场战斗中只能施展一次,但坡旅甲可以按任意顺序施展它们。
例如,假设坡旅甲知道三个法术:力量火法术$$$5$$$、力量闪电法术$$$1$$$和力量闪电法术$$$8$$$。有 $$$6$$$ 方法来选择他施法的顺序:
- 第一,第二,第三。该命令造成 $$$5 + 1 + 2 \cdot 8 = 22$$$ 伤害;
- 第一,第三,第二。该命令造成 $$$5 + 8 + 2 \cdot 1 = 15$$$ 伤害;
- 第二,第一,第三。该命令造成 $$$1 + 2 \cdot 5 + 8 = 19$$$ 伤害;
- 第二,第三,第一。该命令造成 $$$1 + 2 \cdot 8 + 2 \cdot 5 = 27$$$ 伤害;
- 第三,第一,第二。该命令造成 $$$8 + 2 \cdot 5 + 1 = 19$$$ 伤害;
- 第三,第二,第一。该命令造成 $$$8 + 2 \cdot 1 + 2 \cdot 5 = 20$$$ 伤害。
最初,坡旅甲知道 $$$0$$$ 法术。他的咒语集会改变 $$$n$$$ 次,每次他要么学习一个新咒语,要么忘记一个已知的咒语。每次更改后,计算波利卡普使用他所知道的法术可能造成的最大伤害。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 咒语集的更改次数。
接下来的 $$$n$$$ 行包含两个整数 $$$tp$$$ 和 $$$d$$$ ($$$0 \le tp_i \le 1$$$; $$$-10^9 \le d \le 10^9$$$; $$$d_i \neq 0$$$) — 更改的描述。如果 $$$tp_i$$$ 等于 $$$0$$$,则波利卡普学习(或忘记)火咒语,否则他学习(或忘记)闪电咒语。
如果$$$d_i > 0$$$,则坡旅甲学习力量咒语$$$d_i$$$。否则,波利卡普会忘记一个具有 $$$-d_i$$$ 威力的咒语,并且可以保证他在改变之前就知道该咒语。
保证每次改变后波利卡普所知道的所有法术的威力都是不同的(波利卡普永远不会知道具有相同威力的两个法术)。
输出
每次更改后,打印波利卡普可以处理他当前法术集的最大伤害。
示例
输入 #1
6 1 5 0 10 1 -5 0 5 1 11 0 -10
输出 #1
5 25 10 15 36 21