Маленький Т. спроектировал выставочную зону в виде двумерной сетки размера $n \times n$. Самый внешний периметр сетки окружен рядом выставочных стен, то есть все клетки, у которых хотя бы одна из координат равна $0$ или $n+1$, являются клетками выставочных стен. Кроме того, внутри выставочной зоны разбросано $m$ клеток выставочных стен, $i$-я из которых ($1 \le i \le m$) имеет координаты $(x_i, y_i)$. Гарантируется, что все клетки выставочных стен образуют связную структуру по 4 направлениям.

После тестирования на местности Маленький Т. определил правила затрат времени на перемещение между клетками. В частности, существуют следующие два способа перемещения между клетками: Перемещение на одну клетку по вертикали или горизонтали, то есть из $(x, y)$ в одну из соседних клеток $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$, требует $2$ единицы времени. Перемещение на одну клетку по диагонали, то есть из $(x, y)$ в одну из диагональных клеток $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$, требует $3$ единицы времени.

Разумеется, целевая клетка перемещения не может быть клеткой выставочной стены. Примечание: при перемещении по диагонали можно проходить непосредственно через зазор между двумя диагонально расположенными клетками выставочных стен. Например, даже если $(x, y+1)$ и $(x+1, y)$ являются клетками выставочных стен, все равно можно потратить $3$ единицы времени, чтобы переместиться из $(x, y)$ по диагонали в $(x+1, y+1)$.

Маленький С. разместил в выставочной зоне $q$ сокровищ. Для $i$-го сокровища ($1 \le i \le q$) он объявляет его положение $(tx_i, ty_i)$, при этом ваше текущее положение — $(sx_i, sy_i)$. Чтобы как можно быстрее добраться до каждого сокровища, вам нужно вычислить минимальное время, необходимое для перемещения из вашего текущего положения в положение сокровища.

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

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

Далее следуют $m$ строк, $i$-я из которых ($1 \le i \le m$) содержит два целых положительных числа $x_i, y_i$ ($1 \le x_i, y_i \le n$), обозначающих координаты $i$-й клетки выставочной стены. Гарантируется, что все $(x_i, y_i)$ различны.

Далее следуют $q$ строк, $i$-я из которых ($1 \le i \le q$) содержит четыре целых положительных числа $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), обозначающих ваше текущее положение и положение сокровища при объявлении $i$-го сокровища. Гарантируется, что $(sx_i, sy_i)$ и $(tx_i, ty_i)$ не являются клетками выставочных стен.

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

Выведите $q$ строк, в каждой из которых содержится целое число — ответ на задачу. В частности, если вы не можете добраться до положения сокровища, выведите $-1$.

Примеры

Входные данные 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

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

2
16
11
10
11

Примечание 1

Для второго сокровища вы можете перемещаться по следующему пути: $(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$.