题目描述

给定平面上的一个点集，以及 $N$ 个会修改该点集的操作。每个操作属于以下两类之一：

1. 向点集中加入一个整点。新加入点的横坐标，即 $X$ 坐标，严格大于当前点集中所有点的横坐标；
2. 从点集中删除横坐标最大的点。

请编写程序 convex，按照给定的操作序列进行模拟，并在每次操作后输出当前点集凸包面积的两倍。

在第一次操作之前，点集为空。空点集的凸包面积视为 $0$。

输入格式

第一行输入一个正整数 $N$，表示操作数量。

接下来 $N$ 行，每行包含三个整数，表示一条经过加密的操作信息。

对于第 $i$ 个操作，从输入第 $i+1$ 行读入三个数 $T_0,X_0,Y_0$，满足：

$$0 \le T_0 \le 1, \quad 0 \le X_0,Y_0 \le 2\,000\,000\,000.$$

设 $S$ 为执行前 $i-1$ 个操作后当前点集凸包面积的两倍。第一次操作前 $S=0$。可以证明 $S$ 始终为整数。

首先计算：

$$T=(T_0+S)\bmod 2.$$

情况 1：$T=0$

第 $i$ 个操作为加入点。加入点 $(X,Y)$ 的坐标由下式得到：

$$X=L+((S+X_0)\bmod 2\,000\,000\,001),$$ $$Y=((Y_0+S)\bmod 2\,000\,000\,001)-1\,000\,000\,000.$$

其中 $L$ 是当前点集中所有点横坐标的最大值。若当前点集为空，则 $L=-1\,000\,000\,000$。

情况 2：$T=1$

第 $i$ 个操作要求执行 $K$ 次第二类操作，即每次删除当前横坐标最大的点。

$K$ 由下式得到：

$$K=((X_0+Y_0+S)\bmod Q)+1,$$

其中 $Q$ 是当前点集中的点数。

输出格式

输出 $N$ 行。第 $i$ 行输出执行前 $i$ 个操作后，当前点集凸包面积的两倍。

若当前点集为空，输出 $0$。

数据范围

• $1 \le N \le 100\,000$；
• 保证在正确解密全部操作后，满足以下条件：
  • 所有被加入的点的坐标都在 $[-10^9,10^9]$ 范围内；
  • 每次加入新点时，它的横坐标严格大于当前点集中所有点的横坐标；
  • 第二类操作只会在点集非空时执行。

子任务 / 评分说明

每个测试点单独评分。

• $15\%$ 的测试满足 $N \le 300$；
• 另外 $15\%$ 的测试满足 $N \le 3000$；
• 另外 $20\%$ 的测试满足 $N \le 100\,000$，且解密后 $T=1$ 的输入行数不超过 $100$；
• 剩余 $50\%$ 的测试无额外限制。

样例

输入

6
0 1000000000 1000000000
0 1000000 1001000000
0 1000000 999000000
0 1001500 1000001500
1 85072946 2
1 61619603 2

输出

0
0
3000000000000
6000000000000
3000000000000
0

样例说明

解密后，测试等价于：

T = 0, X = 0,       Y = 0
T = 0, X = 1000000, Y = 1000000
T = 0, X = 2000000, Y = -1000000
T = 0, X = 3000000, Y = 0
T = 1, K = 1
T = 1, K = 2