Alice 和 Bob 正在玩 Nim 游戏。在这个游戏中，有若干堆石子，每堆石子可以包含多个。两名玩家轮流从某一堆中取走任意数量的石子。无法进行合法移动的玩家输掉游戏。在每一轮中，玩家可以选择一堆石子，并从中取走正整数个石子。

他们将在接下来的 $n$ 天里进行 $n$ 场游戏，每天一场。初始时没有任何石子堆。在第 $i$ 天，会发生一个事件，随后他们进行一场新的游戏。Alice 总是先手，且双方都会采取最优策略。Bob 想要通过作弊来赢得游戏。在每场游戏开始前，Bob 可以支付一定的费用删除若干堆石子，使得 Alice 永远无法获胜。每场游戏结束后，Bob 会恢复所有被删除的石子堆。

每天会发生以下两种事件之一：

• “ADD $a[i]$ $b[i]$” ($1 \le a[i] < 16\,384$, $1 \le b[i] \le 100\,000$)：Alice 添加一堆包含 $a[i]$ 个石子的新堆作为最右侧的堆，删除该堆需要 Bob 支付 $b[i]$ 美元。
• “DEL”：Alice 移除最右侧的堆。保证该堆一定存在。

作为 Bob 最好的朋友，请帮助 Bob 确定在每场游戏中应该删除哪些石子堆，使得总作弊成本最小化。注意，Bob 总可以通过删除所有石子堆来获胜。

输入格式

输入仅包含一组数据。 第一行包含一个整数 $n$ ($1 \le n \le 40\,000$)，表示天数。 接下来的 $n$ 行描述了事件，第 $i$ 行表示第 $i$ 天发生的事件。 保证 “ADD” 事件的数量不超过 $20\,000$。

输出格式

输出 $n$ 行，其中第 $k$ 行 ($1 \le k \le n$) 包含一个整数，表示 Bob 在第 $k$ 天需要支付的最小美元数。

样例

样例输入 1

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

样例输出 1

10
14
0
1
0
14
4