P6224 [BJWC2014] Data

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.

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 several lines, in order, each being the answer to a query operation.

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