SJY摆棋子

SJY 在一个棋盘上摆放棋子。棋盘上初始有 $N$ 个黑色棋子，之后进行 $M$ 次操作。每次操作会在棋盘上放置一个黑色棋子或白色棋子。

放置白色棋子时，需要找出当前棋盘上距离它最近的黑色棋子。两个坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的棋子之间的曼哈顿距离为：

$$|x_1-x_2|+|y_1-y_2|$$

对于每个被放置的白色棋子，请输出它与当前所有黑色棋子之间的最小曼哈顿距离。同一个格子内可以放置多个棋子。

输入格式

第一行包含两个整数 $N$、$M$，分别表示初始黑色棋子的数量和操作数量。

接下来 $N$ 行，每行包含两个整数 $x$、$y$，表示一个初始黑色棋子的坐标。

接下来 $M$ 行，每行包含三个整数 $t$、$x$、$y$：

• 若 $t=1$，则在坐标 $(x,y)$ 处放置一个黑色棋子；
• 若 $t=2$，则在坐标 $(x,y)$ 处放置一个白色棋子，并查询它到当前所有黑色棋子的最小曼哈顿距离。

输出格式

对于每个满足 $t=2$ 的操作，输出一行一个整数，表示对应白色棋子到当前所有黑色棋子的最小曼哈顿距离。

样例输入

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

样例输出

1
2

数据范围

• $1\le N,M\le 5\times 10^5$；
• 对于所有初始棋子和操作，均有 $0\le x,y\le 10^9$；
• 由于 $N\ge 1$ 且黑色棋子只增加、不删除，因此每次执行 $t=2$ 的操作时，棋盘上都至少存在一个黑色棋子；
• 本题可以使用 KD 树通过。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

1
2