#P17847. [ONTAK 2021]ZAM

[ONTAK 2021]ZAM

城堡

城堡是一个无孔的简单正交多边形,边全部平行于坐标轴,相邻两条边互相垂直。所有顶点均为整数格点,按逆时针顺序给出。

多边形内部以及边界上,所有沿整数网格线的单位线段都是可以行走的走廊。给出 qq 对起终点,均为多边形内部或边界上的整数格点,求每对点之间沿走廊行走的最短距离。

输入格式

第一行偶数 nn,接下来 nn 行,每行给出一个顶点的两个坐标。然后一行 qq,再接下来 qq 行,每行 xA,yA,xB,yBx_A,y_A,x_B,y_B。

输出格式

每个询问输出一行最短距离。

数据范围

4≤n≤1000004\le n\le100000,1≤q≤1000001\le q\le100000。所有坐标为 [0,108][0,10^8] 内的整数。边界没有自交或自接触。起点和终点不同。

样例

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