题目背景

在确定好主会场的位置后，小 T 和小 S 开始着手布置庆典会场。他们在通往主会场的必经之路上，设置了一块宽阔的展览区，用于展现十年 THUPC 的精彩画面。

小 T 将展览区规划成了一个巨大的网格，最外围以及内部的部分格子被设为展览墙。为了方便大家沿动线参观，他将所有的展览墙精心设计为了四连通的结构。

为了让参观过程更具趣味性，小 S 决定在这里举办一场寻宝活动。

题目描述

小 T 将展览区规划成一个大小为 $n \times n$ 的二维网格。网格的最外围由一圈展览墙包围，即横坐标或纵坐标等于 $0$ 或 $n+1$ 的所有格子均为展览墙格子。此外，展览区内部还散布着 $m$ 个展览墙格子，其中第 $i$ ($1 \le i \le m$) 个的坐标为 $(x_i, y_i)$。保证所有的展览墙格子之间是四连通的。

经过实地布景测试，小 T 总结出了在网格间移动的耗时规律。具体而言，在格子间有以下两种移动方式：

• 沿上下左右方向移动一格，即从 $(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)$。

小 S 在展览区中总计布置了 $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 \times 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) \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$。