시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB160412724.107%

문제

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 (x1, y1) and the upper right — (x2, y2). 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 not guarantee that the figures are distinct.

In addition, to fulfill these queries, after each of them, 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 ≤ q ≤ 105) — the number of queries.

Each of the following q lines contains one query:

  • <1 x y> (1 ≤ x, y ≤ 109) — add a point with the coordinates (x, y) to this plane.
  • <2 x1 y1 x2 y2> (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109) — add a rectangle whose left lower corner has the coordinates (x1, y1), and the upper right — (x2, y2).

출력

You need to print out q lines, the i-th line must contain one integer number — the number of pairs of rectangles and points, in which the point lies on the side or inside the rectangle.

예제 입력 1

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

예제 출력 1

0
0
0
3
4

예제 입력 2

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

예제 출력 2

0
0
2
4

예제 입력 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

예제 출력 3

0
0
0
3
6
6
9

힌트

Explanation of the first example:

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

After the second query, we still do not have rectangles, so there are no pairs at all.

Still no rectangles after the third query.

In the fourth query, we added a rectangle with the coordinates of the left lower point (1, 1), and the coordinates of the upper right corner are (5, 5). All three previously added points 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 that was added in the fourth query (the first three pairs) and the pair where the point added in the second query lies inside the rectangle, which was added in the fifth query