Description

To write his thesis, Alex often needs to organize a large amount of data. This time, Alex faces a serious challenge: he needs to implement a data structure to maintain a set of points.

Now there are $N$ points on a 2D plane.

Alex needs to support the following three operations:

1. Add a point to the set.

2. Given a point, query the minimum Manhattan distance from it to all points in the set.

3. Given a point, query the maximum Manhattan distance from it to all points in the set.

The Manhattan distance between two points is defined as the sum of the absolute difference of their $x$-coordinates and the absolute difference of their $y$-coordinates.

Such a difficult problem is of course beyond Alex, so he has to ask you for help again.

Input Format

The first line contains an integer $N$, indicating the initial number of points in the set.

The next $N$ lines each contain two integers, representing the $x$-coordinate and $y$-coordinate of a point.

Line $N + 2$ contains an integer $Q$, indicating the number of queries.

The next $Q$ lines each contain three integers, representing the query type, the $x$-coordinate, and the $y$-coordinate. Type $0$ means adding a point, type $1$ means querying the minimum Manhattan distance to that point, and type $2$ means querying the maximum.

Output Format

Output several lines, in order, each being the answer to a query operation.

3
7 5
6 2
3 1
5
1 6 1
1 5 5
2 7 1
0 3 2
1 1 0

1
2
4
3

Hint

For the first $20\%$ of the testdata: $1 \le N, Q \le 10^3$.

For $100\%$ of the testdata: $1 \le N, Q \le 10^5$.

The coordinates of points are non-negative integers not exceeding $10^9$.

Translated by ChatGPT 5