Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

E. Iqea
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The first line contains one integer n — number of cities in Gridland (1 ≤ n ≤ 300 000). The following n lines contain two integers xi and yi — coordinates of cell that contains i-th city (1 ≤ xi, yi ≤ 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 ≤ q ≤ 300 000). Following q lines contain queries, i-th line consists of three integers ti, xi and yi (ti ∈ {1, 2}, 1 ≤ xi, yi ≤ 300 000). If ti = 1, new Iqea shop has been opened in the city with coordinates (xi, yi). It's guaranteed that there was no Iqea shop in this city before. If ti = 2, you are to find the distance to the nearest already opened Iqea shop from the city with coordinates (xi, yi). It's guaranteed that in queries of both types cell (xi, yi) belongs to Gridland.

Output

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.

Examples
Input
71 21 32 33 13 23 34 252 3 21 4 22 1 21 3 32 2 3
Output
-151
Input
61 11 21 32 12 23 141 3 12 1 21 2 22 1 3
Output
32

Explanation of the first example:

Before all queries

First query

Second query

Third query

Fourth query

Fifth query

Explanation of the second example:

Before all queries

First query

Second query

Third query

Fourth query