Description

Seven years ago, Ayu received an angel doll. She buried it underground as a time capsule. But today, seven years later, Ayu has forgotten where she buried it, so she decides to look for it based only on some vague memories.

We treat the town where Ayu lives as a 2D Cartesian coordinate plane. From time to time, Ayu will recall that the doll might have been buried at some point $(x, y)$; or she will ask you: if she is at $(x, y)$, how far is it to the nearest location where the angel doll might have been buried.

Because Ayu only moves along directions parallel to the coordinate axes, in this problem we define the distance between two points as $\operatorname{dist}(A, B) = |A_x - B_x| + |A_y - B_y|$. Here $A_x$ denotes the $x$-coordinate of point $A$, and similarly for the others.

Input Format

The first line contains two integers $n$ and $m$. At the start, Ayu already knows $n$ points where the doll might be buried, and then she will perform $m$ operations.

The next $n$ lines each contain two non-negative integers $(x_i, y_i)$, denoting the coordinates of the initial $n$ points.

Then the next $m$ lines each contain three non-negative integers $t, x_i, y_i$.

• If $t = 1$, Ayu recalls another point $(x_i, y_i)$ where the doll might be buried.
• If $t = 2$, Ayu asks: if she is at $(x_i, y_i)$, among the points recalled so far, how far is the nearest point to her.

Output Format

For each query with $t = 2$, output the result on a separate line.

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

1 
2

Hint

Constraints: For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 3 \times 10^5$ and $0 \leq x_i, y_i \leq 10^6$.

Translated by ChatGPT 5