CF936E.Iqea

Gridland is placed on infinite grid and has a shape of figure consisting of cells. Every cell of Gridland is a city. Two cities that are placed in adjacent cells are connected by the road of length $1$. It's possible to get from any city to any other city using roads. The distance between two cities is the minimum total road length on path from one city to another. It's possible to get from any cell that doesn't belong to Gridland to any other cell that doesn't belong to Gridland by using only cells which don't belong to Gridland. In other words, Gridland is connected and complement of Gridland is also connected.

At the moment no city in Gridland has Iqea famous shop. But Iqea has great plans for building shops in Gridland. For customers' convenience Iqea decided to develop an application. Using this application everyone can learn the distance to the nearest Iqea. You are to develop this application.

You are asked to process two types of queries:

• new Iqea shop has been opened in the city with coordinates $(x, y)$;
• customer wants to know the distance to the nearest already opened Iqea shop from his city located in a cell with coordinates $(x, y)$.

Pay attention that customer can move only by roads and can never leave Gridland on his way to the shop.

Gridland 位于无限网格上，其形状由若干格子构成。Gridland 中的每个格子都是一座城市。位于相邻格子中的两座城市之间有一条长度为 $1$ 的道路相连。任意两座城市之间均可通过道路相互到达。两座城市之间的距离定义为从一座城市到另一座城市的路径中，道路总长度的最小值。此外，任意两个不属于 Gridland 的格子之间，也可仅通过不属于 Gridland 的格子相互到达。换言之，Gridland 是连通的，且 Gridland 的补集（即所有不属于 Gridland 的格子组成的集合）也是连通的。

目前，Gridland 中尚无 Iqea 著名连锁店。但 Iqea 已制定了在 Gridland 大力开设门店的宏伟计划。为方便顾客，Iqea 决定开发一款应用程序：用户可通过该程序查询到最近一家已开业 Iqea 门店的距离。你被要求实现该应用程序。

你需要处理两类查询：

• 在坐标为 $(x, y)$ 的城市新开设了一家 Iqea 门店；
• 一位顾客希望查询其所在城市（坐标为 $(x, y)$ 的格子）到最近一家已开业 Iqea 门店的距离。

请注意：顾客只能沿道路移动，且在前往门店的整个过程中不得离开 Gridland。

The first line contains one integer $n$ — number of cities in Gridland ($1 \le n \le 300\,000$). The following $n$ lines contain two integers $x_i$ and $y_i$ — coordinates of cell that contains $i$-th city ($1 \le x_i, y_i \le 300\,000$). No two cells coincide. Cells form connected area, complement of this area is also connected.

The following line contains single integer $q$ — number of queries ($0 \le q \le 300\,000$). Following $q$ lines contain queries, $i$-th line consists of three integers $t_i$, $x_i$ and $y_i$ ($t_i \in {1, 2}$, $1 \le x_i, y_i \le 300\,000$). If $t_i = 1$, new Iqea shop has been opened in the city with coordinates $(x_i, y_i)$. It's guaranteed that there was no Iqea shop in this city before. If $t_i = 2$, you are to find the distance to the nearest already opened Iqea shop from the city with coordinates $(x_i, y_i)$. It's guaranteed that in queries of both types cell $(x_i, y_i)$ belongs to 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。

For every query of second type output single integer — minimum distance to the nearest Iqea shop. If no Iqea shop has been already opened, output $-1$.

对于每个第二类查询，输出一个整数——到最近的宜家（Iqea）商店的最小距离。如果尚未开设任何宜家（Iqea）商店，则输出 $-1$。