Points and Rectangles

You have an empty infinite two-dimensional plane and $q$ queries. There are two types of queries:

• <1 x y> — add a point with the coordinates $(x, y)$ to the plane.
• <2 x1 y1 x2 y2> — add a rectangle whose lower left corner has the coordinates $(x_1, y_1)$ and whose upper right corner has the coordinates $(x_2, y_2)$. The area of this rectangle can be zero, and a rectangle can degenerate into a point.

Rectangles and points may overlap, that is, there is no guarantee that the figures are distinct.

After each query, you need to print the number of pairs of rectangles and points in which the point lies on the border or inside the rectangle.

The first line contains one integer $q$ ($1 \le q \le 10^5$), the number of queries.

Each of the following $q$ lines contains one query:

• <1 x y> ($1 \le x, y \le 10^9$) — add a point with the coordinates $(x, y)$ to the plane.
• <2 x1 y1 x2 y2> ($1 \le x_1 \le x_2 \le 10^9$, $1 \le y_1 \le y_2 \le 10^9$) — add a rectangle whose lower left corner has the coordinates $(x_1, y_1)$ and whose upper right corner has the coordinates $(x_2, y_2)$.

Print $q$ lines. The $i$-th line must contain one integer, the number of pairs of rectangles and points in which the point lies on the side or inside the rectangle.

Explanation of the first example:

After the first query, we have one point with the coordinates $(2, 3)$ and no rectangles at all, so there are no pairs of points and rectangles.

After the second query, we still have no rectangles, so there are no pairs.

There are still no rectangles after the third query.

In the fourth query, we added a rectangle whose lower left point has the coordinates $(1, 1)$ and whose upper right corner has the coordinates $(5, 5)$. All three points added earlier lie inside this rectangle, so we have three pairs.

After the fifth query, we have four pairs: the points added during the first three queries lie inside the rectangle added in the fourth query (the first three pairs), and the point added in the second query lies inside the rectangle added in the fifth query (the fourth pair).