| Codeforces Round 467 (Div. 1) |
|---|
| Закончено |
Страна Гридландия располагается на бесконечном клетчатом поле и имеет форму клетчатой фигуры. Каждая клетка Гридландии является городом. Города, находящиеся в соседних по сторонам клетках, соединены дорогой длины $$$1$$$. Из любого города Гридландии можно добраться до любого другого города Гридландии, перемещаясь по дорогам. Расстоянием между двумя городами является минимальная суммарная длина дорог, переместившись по которым можно добраться от одного города до другого. А также из любой клетки, не принадлежащей Гридландии, можно добраться до любой другой клетки, не принадлежащей Гридландии, перемещаясь только по клеткам, не принадлежащим Гридландии, в соседние по стороне клетки. Иными словами, Гридландия связна и дополнение Гридландии связно.
На данный момент ни в одном городе Гридландии нет магазинов популярной сети Iqea. Но у Iqea имеются большие планы по строительству сети магазинов в Гридландии. Для удобства покупателей Iqea решила разработать приложение, в котором житель любого города сможет узнать расстояние до ближайшего магазина Iqea. Вам поручили написать это приложение.
Вам будут поступать запросы двух типов:
- в городе, находящемся в клетке с координатами $$$(x, y)$$$, открылся магазин Iqea;
- покупатель хочет узнать, каково минимальное расстояние до одного из уже открытых магазинов Iqea от его родного города, находящегося в клетке $$$(x, y)$$$.
Обратите внимание, что покупатель может перемещаться только по дорогам и никогда не может покидать территорию Гридландии по пути до магазина.
В первой строке дано одно целое число $$$n$$$ — количество городов в Гридландии ($$$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)$$$ принадлежит Гридландии.
На каждый запрос второго типа выведите в новой строке одно число — искомое минимальное расстояние. Если ни один магазин 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
Пояснение к первому примеру:
До всех запросов 
Первый запрос 
Второй запрос 
Третий запрос 
Четвертый запрос 
Пятый запрос 
Пояснение ко второму примеру:
До всех запросов 
Первый запрос 
Второй запрос 
Третий запрос 
Четвертый запрос 
