有一个 $$$(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 52 12 23 23 31 1 1 21 1 3 14 1 1 44 4 1 12 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$$$。