题目描述

学校把一些地点记录在平面坐标系中。开始时，系统里已经有 $n$ 个已登记地点；之后还会不断收到新的登记，或者收到一次距离查询。

一次距离查询会给出当前位置 $(x,y)$，你需要回答它到所有已登记地点中的最近距离。这里的移动只能沿水平或竖直方向进行，因此两点 $A,B$ 的距离定义为

新增登记会立刻生效，之后的查询都应把它计入。

输入格式

第一行包含两个整数 $n,m$，表示初始登记地点数量和之后的操作数量。

接下来 $n$ 行，每行两个非负整数 $x_i,y_i$，表示一个初始地点。

接下来 $m$ 行，每行三个非负整数 $t,x_i,y_i$：

• 若 $t=1$，表示新增一个登记地点 $(x_i,y_i)$；
• 若 $t=2$，表示询问点 $(x_i,y_i)$ 到当前所有登记地点的最近距离。

输出格式

对于每个 $t=2$ 的询问，输出一行一个整数，表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

1 
2

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 3\times 10^5$，$0\le x_i,y_i\le 10^6$。