Gridland 放置在无限网格上,具有由单元组成的图形形状。 Gridland 的每个单元格都是一座城市。位于相邻单元格中的两个城市通过长度为 $$$1$$$ 的道路连接起来。可以通过道路从任何城市前往任何其他城市。的 距离 两个城市之间的道路是从一个城市到另一个城市的最小道路总长度。通过仅使用不属于 Gridland 的单元格,可以从任何不属于 Gridland 的单元格获取不属于 Gridland 的任何其他单元格。换句话说,Gridland 是连通的,Gridland 的补充也是连通的。
目前Gridland没有哪个城市有Iqea名店。但 Iqea 制定了在 Gridland 开设商店的宏伟计划。为了方便客户,Iqea 决定开发一个应用程序。使用此应用程序,每个人都可以了解到最近的 Iqea 的距离。您将开发此应用程序。
您需要处理两种类型的查询:
- 新的 Iqea 商店已在城市开业,坐标为 $$$(x, y)$$$;
- 客户想知道距离他的城市最近的已开业 Iqea 商店的距离,该商店位于坐标为 $$$(x, y)$$$ 的单元格中。
请注意,顾客只能通过道路移动,并且在前往商店的途中永远不能离开 Gridland。
输入
第一行包含一个整数 $$$n$$$ — Gridland 中的城市数量 ($$$1 \le n \le 300\,000$$$)。以下 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 包含第 $$$i$$$ 城市的像元坐标 ($$$1 \le x_i, y_i \le 300\,000$$$)。没有两个细胞重合。细胞形成连通区域,该区域的补体也是连通的。
以下行包含单个整数 $$$q$$$ — 查询数 ($$$0 \le q \le 300\,000$$$)。以下 $$$q$$$ 行包含查询,第 $$$i$$$ 行由三个整数 $$$t_i$$$、$$$x_i$$$ 和 $$$y_i$$$ 组成($$$t_i \in \{1, 2\}$$$, $$$1 \le x_i, y_i \le 300\,000$$$)。如果 $$$t_i = 1$$$,则表示坐标为 $$$(x_i, y_i)$$$ 的城市已开设新的 Iqea 商店。可以肯定的是,这个城市以前没有Iqea店。如果 $$$t_i = 2$$$,您需要找到从坐标为 $$$(x_i, y_i)$$$ 的城市到最近的已开业 Iqea 商店的距离。保证在两种类型的查询中单元格 $$$(x_i, y_i)$$$ 属于 Gridland。
输出
对于第二类型的每个查询,输出单个整数 - 到最近的 Iqea 商店的最小距离。如果尚未开设 Iqea 商店,则输出 $$$-1$$$。
示例
输入复制
7
1 2
1 3
2 3
3 1
3 2
3 3
4 2
5
2 3 2
1 4 2
2 1 2
1 3 3
2 2 3
输出复制
-1
5
1
输入复制
6
1 1
1 2
1 3
2 1
2 2
3 1
4
1 3 1
2 1 2
1 2 2
2 1 3
输出复制
3
2
第一个例子的解释:
在所有查询之前 
第一次查询 
第二次查询 
第三次查询 
第四次查询 
第五查询 
第二个例子的解释:
在所有查询之前 
第一次查询 
第二次查询 
第三次查询 
第四次查询 