说明

古代丝绸之路的一部分穿过哈萨克斯坦南部。你一直在幻想一条现代化的丝绸之路，它有着自己独特的特色。在你幻想的道路上，有机器人以及储存着坚戈（哈萨克斯坦的国家货币）的商店。如果一个机器人移动到一个有商店的位置，它会为你收集该商店里的所有坚戈。

移动机器人的成本是每移动一米花费 1 坚戈。因此，移动一个机器人到商店所获得的利润是商店拥有的坚戈数量减去机器人移动到商店所需的米数。

考虑这样一个场景，持续数天。最初，道路上空无一物，既没有机器人也没有商店。每天，要么有一个新的机器人，要么有一个新的商店被放置在道路上一个未被占用的位置。在此之前，道路上现有的每个商店都会被重新补给坚戈，使其总量恢复到最初放置在道路上时的数量，同时每个机器人都会被返回到其原始起始位置。

对于每一天，你需要确定通过移动机器人从商店中收集坚戈所能获得的最大利润。注意，没有两个机器人会在同一位点开始，但它们在移动时可能会占据同一位点。每个商店在一天内只能被清空一次坚戈。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^{5})$，表示天数。接下来有 $n$ 行，其中第 $i$ 行以一个整数 $t_{i}$ 开头，如果在第 $i$ 天添加一个新机器人，则 $t_{i}$ 等于 $1$；如果添加一个新商店，则 $t_{i}$ 等于 $2$。随后是一个整数 $x_{i}$ $(0 \leq x_{i} \leq 10^{8})$，表示新机器人或新商店的位置。如果 $t_{i}=2$，该行还包含另一个整数 $c_{i}$ $(0 \leq c_{i} \leq 10^{8})$，表示商店中的坚戈数量。所有给定的位置都是不同的。

输出格式

输出 $n$ 个整数，表示每天之后你能获得的最大利润。

6
1 20
2 15 15
2 40 50
1 50
2 80 20
2 70 30

0
10
35
50
50
60