Problem Description

Given an empty two-dimensional plane, you are provided with $q$ queries. There are two types of queries:

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

Points and rectangles may overlap.

After each query operation, calculate the number of point-rectangle pairs where the point is inside or on the boundary of the rectangle.

Input Format

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

The following $q$ lines each describe a query:

• $1 \ x \ y \ (1 \leq x, y \leq 10^9)$ — Add a point at 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 with the bottom-left corner at $(x_1, y_1)$ and the top-right corner at $(x_2, y_2)$.

Output Format

You need to output $q$ lines, with the $i$-th line containing an integer representing the number of point-rectangle pairs where the point is inside or on the boundary of the rectangle.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0
0
0
3
4

Input Sample #2

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

Output Sample #2

0
0
2
4

Input Sample #3

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

Output Sample #3

0
0
0
3
6
6
9

Notes

Explanation of the first sample:

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

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

After the third query operation, there are still no rectangles.

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

After the fifth query operation, there are $4$ such pairs: the previous $3$ pairs, plus the additional pair formed by the point added in the second query within the rectangle added in the fifth query.

见题面 Input 部分

见题面 Output 部分