Point Set Manhattan Distance Queries

Alex needs to maintain a set of points on a two-dimensional plane for his research paper. Initially, there are \(N\) points. He needs to support the following three operations:

1. Add a new point to the set.
2. Given a query point, compute the minimum Manhattan distance to all points in the set.
3. Given a query point, compute the maximum Manhattan distance to all points in the set.

The Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is defined as \( |x_1 - x_2| + |y_1 - y_2| \).

inputFormat

The first line contains two integers \(N\) and \(Q\) representing the initial number of points and the number of operations.

The next \(N\) lines each contain two integers \(x\) and \(y\) denoting the coordinates of a point.

The following \(Q\) lines describe an operation in one of the following formats:

• 1 x y: Add the point \((x,y)\) to the set.
• 2 x y: Query for the minimum Manhattan distance from point \((x,y)\) to any point in the set.
• 3 x y: Query for the maximum Manhattan distance from point \((x,y)\) to any point in the set.

outputFormat

For each operation of type 2 and 3, output the corresponding answer on a new line.

sample

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

1
14
8
18