题目描述

Farmer John 的 $N$ 头奶牛，每头都喜欢日常沿围着牧场的栅栏散步。

栅栏甶 $P$根柱子组成，每根柱子的位置是 $FJ$ 农场地图上的一个不同的二维坐标点$(x,y)$。

每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 $x$轴或 $y$轴的一个多边形(最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环)。

栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点(可能在柱子处，也可能不在)。

每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。由于栅栏形成闭环，奶牛有两条路线可以选择。

由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走(如果并列，奶牛可以选择任一方向)。

求每头奶牛行走的距离。

输入

输入的第一行包含 $N$ 和 $P$。

以下 $P$ 行的每一行包含两个整数，以顺时针或逆时针顺序表示栅栏柱子的位置。

以下 $N$行的每一行包含四个整数 $x_1,y_1,x_2,y_2$，表示一头奶牛的起始位置$(x_1,y_1)$和结束位置$(x_2,y_2)$。

输出

输出 $N$ 个整数，为每头奶牛行走的距离。

5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0

2
3
3
4
4

提示

第一头奶牛可以直接从$(0,0)$走到$(0,2)$。

第二头奶牛可以从$(0,2)$走到$(0,0)$，然后走到$(1,0)$。

第四头奶牛有两条长度相等的可能路线:$(1,0)→(0,0)→(0,2)→(1,2)和(1,0)→(2,0)→(2,2)→(1,2)$

提示

测试点$2-6:0≤x,y≤100且N<100.$

测试点$7-11:$。 $1 \leq N \leq 10^5$

$4 \leq P \leq 2 \times 10^5,P$是偶数

$0 \leq x,y \leq 1000$