你正计划带着你的新产品进入市场，但你需要选择合适的时机。为了做到这一点，你正在监控产品的需求。具体来说，你知道所有潜在买家，并且对于每个买家，你都知道他们愿意支付的最高价格 $p_i$。当你进入市场时，你需要选择一个价格 $p$ 来销售你的产品。所有愿意支付该价格及以上（即 $p_i \ge p$）的买家都会购买你的产品，每人支付 $p$；其他人则不会购买。假设生产成本可以忽略不计，你希望最大化你的收入，即 $p$ 乘以愿意支付至少 $p$ 的买家数量。

然而，需求并非一成不变，因此你需要估算多种不同情况下的最大收入。我们将通过若干对 $(p_j, n_j)$ 来描述需求的变化，其中 $p_j$ 表示需求发生变化的最高价格，$n_j$ 表示该价格下需求的变化量。$n_j$ 可能是负数，这意味着之前愿意购买的某些买家不再愿意购买，但愿意支付该最高价格的买家总数始终保持非负。

你需要计算每次需求变化后可能获得的最大收入。

输入格式

输入文件的第一行包含一个整数 $k$ ($1 \le k \le 15 \cdot 10^4$)，表示需求变化的次数。 接下来的 $k$ 行，每行包含两个空格分隔的整数 $p_j$ 和 $n_j$ ($1 \le p_j \le 10^5$, $-10^6 \le n_j \le 10^6$)，分别表示需求发生变化的最高价格，以及该价格下需求的变化量。初始时，对你的产品没有需求。

输出格式

输出 $k$ 个整数，每行一个：在每次需求变化后，输出当前市场情况下的最大可能收入。

样例

输入 1

5
4 2
7 2
7 1
7 -1
4 -2

输出 1

8
16
21
16
14

说明

让我们研究一下这个样例。最初没有需求，然后有两个愿意支付 4 的买家出现。此时，以价格 4 出售是最佳选择，收入为 8。接着，又有两个买家出现，他们愿意支付 7。现在有两种可能的策略：以价格 4 出售，卖出 4 个单位，收入为 16；或者以价格 7 出售，卖出 2 个单位，收入为 14。显然，第一种策略更好。现在又有一个愿意支付 7 的买家出现，突然间以价格 7 出售变得更好，收入为 21（此时以价格 4 出售仅能获得 20）。然后，那个买家消失了，驱动最优解回到了 16。最后，愿意支付 4 的买家中有两个消失了，留给我们的最优策略是以 7 的价格卖给剩下的两个买家，收入为 14。