题目描述

这天，SJY 显得无聊。在家自己玩。在一个棋盘上，有 $N$ 个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即（$\left| x_1-x_2 \right|+\left| y_1-y_2 \right|$）。现在给出 $N$ 个初始棋子。和 $M$ 个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

输入格式

第一行两个数 $N,M$。
之后 $N$ 行，每行 2 个数表示棋子的位置 $x_i,y_i$。
以后 $M$ 行，每行 3 个数 $t,x,y$。
如果 $t=1$ 那么放下一个黑色棋子。
如果 $t=2$ 那么放下一个白色棋子。

输出格式

对于每个 $T=2$ 输出一个最小距离。

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

1
2

数据规模与约定

对于 $100\%$ 的数据，$1 \leq N \leq 500000$，$1 \leq M \leq 500000$。

提示

kdtree可以过

题目来源

鸣谢 孙嘉裕