G. Лабиринт
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Есть сетка размера $$$(n+2) \times (n+2)$$$, где обе координаты принимают значения от $$$0$$$ до $$$n+1$$$ включительно. Все клетки по внешней границе сетки являются клетками-препятствиями.

Кроме того, в сетке есть ещё $$$m$$$ клеток-препятствий. $$$i$$$-я клетка-препятствие находится в точке $$$(x_i, y_i)$$$. Гарантируется, что все препятствия (включая клетки внешней границы) 4-связны. То есть из любой клетки-препятствия можно добраться до любой другой, перемещаясь вверх, вниз, влево или вправо через другие клетки-препятствия.

Маленький L гуляет по этому лабиринту. Он не может заходить ни в одну клетку-препятствие. Если Маленький L находится в позиции $$$(x, y)$$$, он может сделать следующие ходы:

  • Перейти по ортогонали в соседнюю клетку $$$(x+1,y)$$$, $$$(x-1,y)$$$, $$$(x,y+1)$$$ или $$$(x,y-1)$$$ за цену $$$2$$$.
  • Перейти по диагонали в соседнюю клетку $$$(x+1,y+1)$$$, $$$(x+1,y-1)$$$, $$$(x-1,y+1)$$$ или $$$(x-1,y-1)$$$ за цену $$$3$$$.

Есть $$$q$$$ запросов. Для каждого запроса заданы начальная и конечная точки. Нужно найти минимальную суммарную стоимость пути Маленького L из начальной точки в конечную. Если добраться до конечной точки невозможно, выведите $$$-1$$$.

Входные данные

В первой строке входных данных содержатся три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m, q \le 3 \cdot 10^5$$$).

Следующие $$$m$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-й клетки-препятствия. Гарантируется, что все координаты препятствий различны, и что все препятствия (включая клетки внешней границы) 4-связны.

Следующие $$$q$$$ строк содержат по четыре целых числа $$$s_x$$$, $$$s_y$$$, $$$t_x$$$ и $$$t_y$$$ — запрос с начальной точкой $$$(s_x, s_y)$$$ и конечной точкой $$$(t_x, t_y)$$$. Гарантируется, что ни $$$(s_x,s_y)$$$, ни $$$(t_x,t_y)$$$ не являются клетками-препятствиями.

Выходные данные

Для каждого запроса выведите одно целое число — минимальную стоимость пути из начальной точки в конечную. Или выведите $$$-1$$$, если такого пути нет.

Пример
Входные данные
4 4 5
2 1
2 2
3 2
3 3
1 1 1 2
1 1 3 1
4 1 1 4
4 4 1 1
2 3 3 1
Выходные данные
2
16
11
10
11
Примечание

Для второго запроса можно пройти следующим образом: $$$(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$$$. Общая стоимость равна $$$2 + 3 + 3 + 3 + 2 + 3 = 16$$$.