Convex Hull (Queries)

Given a set of points on a plane and $N$ operations that modify this set, each operation can be one of the following two types:

1. Add a point with integer coordinates to the set. The $X$ coordinate of the new point must be strictly greater than the $X$ coordinates of all other points already in the set.

2. Remove the point with the largest $X$ coordinate from the set.

Write a program that simulates these $N$ operations and outputs the doubled area of the convex hull of the set of points after each operation. Initially, the set of points is empty. Assume that the area of the convex hull of an empty set of points is zero.

The convex hull of a set of points on a plane is the smallest convex polygon that contains all the points in the set. A polygon is convex if the line segment connecting any two of its points lies entirely within the polygon. Here, a polygon includes both its boundary and interior.

Input

The first line contains a single integer: $N(1\le N\le 100,000)$ – the number of operations to be performed. The next $N$ lines each contain three integers, representing the operations in an encoded format. To determine the parameters of operation number $i$, read three integers $T\ast$, $X\ast$, and $Y\ast$ $(0\le T\ast \le 1,0\le X\ast ,Y\ast \le 2,000,000,000)$ from the $(i+1)$-th line, then calculate $T$ using the formula: $T=(T\ast +S)\mathrm{mod}2$, where $S$ is the doubled area of the convex hull of the set of points before executing operation $i$. It is guaranteed that $S$ is always an integer.

1. If $T=0$, the current operation is of the first type, and the coordinates $(X,Y)$ of the new point are calculated as follows:

   • $X=L+((S+X\ast )\mathrm{mod}2,000,000,001)$,

   • $Y=((Y\ast +S)\mathrm{mod}2,000,000,001)-1,000,000,000$.

   Here, $L$ is the maximum $X$ coordinate of all points in the set. If the set is empty, then $L=-1,000,000,000$.

2. If $T=1$, perform the second type of operation $K$ times. The number $K$ is determined by the formula: $K=((X\ast +Y\ast +S)\mathrm{mod}Q)+1$. Here, $Q$ is the number of points in the set.

It is guaranteed that with the correct decoding of all operations, the following constraints are met:

1. The coordinates of all points added to the set do not exceed $1,000,000,000$ in absolute value.

2. When adding a new point, its $X$ coordinate is strictly greater than the $X$ coordinates of all points already in the set.

3. The removal operation is applied only to a non-empty set of points.

Output

You need to output exactly $N$ lines. On line $i$, output the doubled area of the convex hull of the set of points formed after executing the first $i$ operations. If the set of points is empty, consider the area of its convex hull to be 0.

Examples

Note

After decoding, the test looks like this:

• $T=0,X=0,Y=0$

• $T=0,X=1,000,000,Y=1,000,000$

• $T=0,X=2,000,000,Y=-1,000,000$

• $T=0,X=3,000,000,Y=0$

• $T=1,K=1$

• $T=1,K=2$

Scoring

The test set consists of 4 separate blocks, with the following additional constraints:

• 15% of tests: $N\le 300$

• 15% of tests: $N\le 3000$

• 20% of tests $N\le 100,000$, with no more than 100 lines where $T=1$ (after decoding)

• 50% of tests: $N\le 100,000$