English · Original
Chinese · Translation
Formal · Original
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 \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.
## 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$.
[samples]
[{"iden":"statement","content":"Gridland 位于无限网格上，其形状是由若干单元格组成的图形。Gridland 的每个单元格都是一座城市。位于相邻单元格的两座城市通过一条长度为 $1$ 的道路连接。任意两座城市之间都可以通过道路相互到达。两个城市之间的 #cf_span(class=[tex-font-style-underline], body=[distance]) 定义为从一座城市到另一座城市的最短路径上道路的总长度。任意不属于 Gridland 的单元格都可以仅通过其他不属于 Gridland 的单元格到达其他不属于 Gridland 的单元格。换句话说，Gridland 是连通的，且其补集也是连通的。\n\n目前，Gridland 中没有任何城市设有 Iqea 著名商店。但 Iqea 计划在 Gridland 中建设商店。为了方便顾客，Iqea 决定开发一款应用程序，任何人都可以通过该应用查询到最近的 Iqea 商店的距离。你需要开发这个应用程序。\n\n你需要处理两种类型的查询：\n\n请注意，顾客只能沿道路移动，且在前往商店的途中绝不能离开 Gridland。\n\n第一行包含一个整数 $n$ — Gridland 中的城市数量（$1 lt.eq n lt.eq 300 thin 000$）。接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$ — 第 $i$ 座城市所在单元格的坐标（$1 lt.eq x_i, y_i lt.eq 300 thin 000$）。没有两个单元格重合。这些单元格构成一个连通区域，该区域的补集也是连通的。\n\n接下来一行包含一个整数 $q$ — 查询数量（$0 lt.eq q lt.eq 300 thin 000$）。接下来的 $q$ 行包含查询，第 $i$ 行包含三个整数 $t_i$, $x_i$, $y_i$（$t_i in {1, 2}$，$1 lt.eq x_i, y_i lt.eq 300 thin 000$）。如果 $t_i = 1$，表示在坐标为 $(x_i, y_i)$ 的城市新开设了一家 Iqea 商店。保证该城市之前没有 Iqea 商店。如果 $t_i = 2$，你需要求出从坐标为 $(x_i, y_i)$ 的城市到已开设的最近 Iqea 商店的距离。保证在两种类型的查询中，单元格 $(x_i, y_i)$ 都属于 Gridland。\n\n对于每个第二类查询，输出一个整数 — 到最近 Iqea 商店的最小距离。如果尚未开设任何 Iqea 商店，则输出 $-1$。\n\n第一个示例的说明：\n\n所有查询之前 \n\n第一次查询 \n\n第二次查询 \n\n第三次查询 \n\n第四次查询 \n\n第五次查询 \n\n第二个示例的说明：\n\n所有查询之前 \n\n第一次查询 \n\n第二次查询 \n\n第三次查询 \n\n第四次查询 \n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ — Gridland 中的城市数量（$1 lt.eq n lt.eq 300 thin 000$）。接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$ — 第 $i$ 座城市所在单元格的坐标（$1 lt.eq x_i, y_i lt.eq 300 thin 000$）。没有两个单元格重合。这些单元格构成一个连通区域，该区域的补集也是连通的。接下来一行包含一个整数 $q$ — 查询数量（$0 lt.eq q lt.eq 300 thin 000$）。接下来的 $q$ 行包含查询，第 $i$ 行包含三个整数 $t_i$, $x_i$, $y_i$（$t_i in {1, 2}$，$1 lt.eq x_i, y_i lt.eq 300 thin 000$）。如果 $t_i = 1$，表示在坐标为 $(x_i, y_i)$ 的城市新开设了一家 Iqea 商店。保证该城市之前没有 Iqea 商店。如果 $t_i = 2$，你需要求出从坐标为 $(x_i, y_i)$ 的城市到已开设的最近 Iqea 商店的距离。保证在两种类型的查询中，单元格 $(x_i, y_i)$ 都属于 Gridland。"},{"iden":"output","content":"对于每个第二类查询，输出一个整数 — 到最近 Iqea 商店的最小距离。如果尚未开设任何 Iqea 商店，则输出 $-1$。"},{"iden":"examples","content":"输入\n7\n1 2\n1 3\n2 3\n3 1\n3 2\n3 3\n4 2\n5\n2 3 2\n1 4 2\n2 1 2\n1 3 3\n2 2 3\n输出\n-1\n5\n1\n\n输入\n6\n1 1\n1 2\n1 3\n2 1\n2 2\n3 1\n4\n1 3 1\n2 1 2\n1 2 2\n2 1 3\n输出\n3\n2\n\n第一个示例的说明：\n所有查询之前 \n第一次查询 \n第二次查询 \n第三次查询 \n第四次查询 \n第五次查询 \n\n第二个示例的说明：\n所有查询之前 \n第一次查询 \n第二次查询 \n第三次查询 \n第四次查询 "}]}
**Definitions:**
- Let $ G \subset \mathbb{Z}^2 $ be a finite set of grid points (cities) forming a connected subset of the infinite grid, such that $ \mathbb{Z}^2 \setminus G $ is also connected.
- The distance between two cities $ u, v \in G $ is the Manhattan distance along the grid:
$$
d(u, v) = |x_u - x_v| + |y_u - y_v|
$$
(since movement is restricted to adjacent grid cells and the grid is unobstructed within $ G $, and $ G $ is connected, the shortest path is the Manhattan path within $ G $).
- Let $ S \subseteq G $ be the set of cities that contain an Iqea shop (initially empty).
**Input:**
- $ n $: number of cities in $ G $.
- $ G = \{ (x_i, y_i) \mid i = 1, \dots, n \} $: set of coordinates of cities.
- $ q $: number of queries.
**Queries:**
For each query $ i $, given $ (t_i, x_i, y_i) $:
- If $ t_i = 1 $: insert point $ p = (x_i, y_i) $ into $ S $ (guaranteed $ p \in G $ and $ p \notin S $ before).
- If $ t_i = 2 $: compute
$$
\min_{s \in S} d(p, s), \quad \text{where } p = (x_i, y_i) \in G
$$
If $ S = \emptyset $, output $ -1 $.
**Output:**
For each query of type 2, output the minimum Manhattan distance from $ p $ to any shop in $ S $, or $ -1 $ if $ S = \emptyset $.
---
**Formal Problem Statement:**
Let $ G \subset \mathbb{Z}^2 $ be a finite, connected set of grid points with connected complement.
Let $ S \subseteq G $ be a dynamically evolving subset (initially $ S = \emptyset $).
Process $ q $ queries of two types:
1. $ \texttt{1 } x \texttt{ } y $: Insert $ (x, y) \in G $ into $ S $.
2. $ \texttt{2 } x \texttt{ } y $: Output $ \min_{s \in S} (|x - s_x| + |y - s_y|) $ if $ S \neq \emptyset $, else $ -1 $.
All points in queries belong to $ G $.
API Response (JSON)
{
"problem": {
"name": "E. Iqea",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF936E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Gridland 位于无限网格上，其形状是由若干单元格组成的图形。Gridland 的每个单元格都是一座城市。位于相邻单元格的两座城市通过一条长度为 $1$ 的道路连接。任意两座城市之间都可以通过道路相互到达。两个城市之间的 #cf_span(class=[tex-font-style-underline], body=[distan...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ G \\subset \\mathbb{Z}^2 $ be a finite set of grid points (cities) forming a connected subset of the infinite grid, such that $ \\mathbb{Z}^2 \\setminus G $ is also connected.\n- ...",
"is_translate": false,
"language": "Formal"
}
]
}