Description

You are given an empty 2D plane and $q$ queries. There are two types of queries:

• $1 \ x \ y$ — Add a point with coordinates $(x,y)$ to the plane.
• $2 \ x_1 \ y_1 \ x_2 \ y_2$ — Add a rectangle whose bottom-left corner is $(x_1,y_1)$ and top-right corner is $(x_2,y_2)$. The area of the rectangle can be $0$, and the rectangle may degenerate into a point.

Rectangles and points may overlap.

After each query is processed, compute the number of point-rectangle pairs such that the point is inside the rectangle or on its boundary.

Input Format

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

The next $q$ lines each describe one query:

• $1 \ x \ y \ (1 \leq x,y \leq 10^9)$ — Add a point with coordinates $(x,y)$ to the plane.
• $2 \ x_1 \ y_1 \ x_2 \ y_2 \ (1 \leq x_1 \leq x_2 \leq 10^9, 1 \leq y_1 \leq y_2 \leq 10^9)$ — Add a rectangle whose bottom-left corner is $(x_1,y_1)$ and top-right corner is $(x_2,y_2)$.

Output Format

Output $q$ lines. The $i$-th line should contain one integer, representing the number of point-rectangle pairs such that the point is inside the rectangle or on its boundary.

5
1 2 3
1 2 2
1 3 4
2 1 1 5 5
2 2 2 2 2

0
0
0
3
4

4
2 1 1 3 3
2 1 1 2 2
1 2 2
1 2 2

0
0
2
4

7
1 5 5
1 5 5
1 5 5
2 2 2 9 9
2 1 1 5 5
2 1 1 2 2
1 2 2

0
0
0
3
6
6
9

Hint

Explanation of the first sample:

After the first query, there is one point $(2,3)$ on the plane, but there are no rectangles, so there are no valid point-rectangle pairs.

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

After the third query, there are still no rectangles.

In the fourth query, we add a rectangle with bottom-left corner $(1,1)$ and top-right corner $(5,5)$. All points added before are inside this rectangle, so there are $3$ such pairs.

After the fifth query, we have $4$ such pairs: the $3$ pairs above, plus $1$ new pair where the point inserted in the second query lies inside the rectangle inserted in the fifth query.

Translated by ChatGPT 5