题目描述

一群寻宝者得到了一张古老城堡的地图。城堡地下藏着宝藏。

地图绘制在一张整数方格网上，左下角为 $(0,0)$，右上角为 $(W,W)$。

城堡在地图上是一个简单正交多边形：

• 所有顶点坐标均为整数；
• 每条边都沿网格线；
• 相邻两条边互相垂直；
• 边界是一条简单闭合折线，即除了相邻边的公共端点外不会发生自交。

所有完全包含在该多边形内部或边界上的单位网格边都代表城堡的地下走廊。也就是说，人只能沿水平或竖直的网格边移动，每走过一条单位网格边的代价为 $1$。

地图上还标出了若干次寻宝任务。每次任务给定：

• 地下城入口点 $A=(x_A,y_A)$；
• 宝藏所在点 $B=(x_B,y_B)$。

两个点都位于多边形内部或边界上。

对于每次询问，请求出沿地下走廊从 $A$ 到 $B$ 的最短路长度。

输入格式

第一行包含一个偶数 $n$，表示正交多边形的顶点数。

接下来 $n$ 行，第 $i$ 行包含整数 $x_i,y_i$，表示多边形顶点。顶点按逆时针顺序给出：

$0\le x_i,y_i\le W$。

随后一行包含整数 $q$，表示询问数。

接下来 $q$ 行，每行包含四个整数：

$x_A\ y_A\ x_B\ y_B$，

表示入口点 $A$ 和宝藏点 $B$。

两个点均位于多边形内部或边界上。

完整数据满足：

• $4\le n\le100000$；
• $1\le W\le10^9$；
• $1\le q\le100000$。

输出格式

输出 $q$ 行。

第 $i$ 行输出第 $i$ 个询问中，从入口点到宝藏点沿合法网格走廊移动的最短距离。

样例

10
9 6
9 2
12 2
12 9
2 9
2 1
8 1
8 3
4 3
4 6
2
11 5 3 1
10 4 10 8

14
4

子任务

所有子任务均满足 $4\le n\le100000$、$1\le W\le10^9$、$1\le q\le100000$。