测试数据来自 system/2927

作业已超过截止时间，您无法递交本题目。

散步

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　花园小区的 \(N（1≤N≤10^5）\) 个居民都喜欢日常沿小区的围墙散步。

　　小区围墙由 \(M（4≤M≤2⋅10^5，M 为偶数）\) 根柱子组成，每根柱子的位置是花园小区地图上的一个不同的二维坐标点 \((x,y)（0≤x,y≤1000）\)。每根柱子通过垂直或水平一段围墙连接到两根相邻的柱子，因此整个小区围墙可以被视为各边平行于 \(x\) 轴或 \(y\) 轴的一个多边形（最后一根柱子连回第一根柱子，确保围墙形成一个包围小区的闭环）。小区围墙多边形，且每一段围墙段仅可能在其端点处重合，每根柱子恰好属于两个围墙段，同时每两个在端点处相交的围墙段都是垂直的。

　　每个居民的日常散步都有一个起始和结束位置，均为沿小区围墙的某个点（可能在柱子处，也可能不在）。每个居民日常散步时沿着小区围墙行走，从起始位置开始，到结束位置结束。由于小区围墙形成闭环，居民有两条路线可以选择，他们会选择距离较长的方向沿小区围墙行走（如果并列，居民可以选择任一方向）。

　　请编程求出每个居民行走的距离。

【输入格式】

　　输入的第一行包含 \(N\) 和 \(M\)。
　　以下 \(M\) 行的每一行包含两个整数，以顺时针或逆时针顺序表示小区围墙柱子的位置。
　　以下 \(N\) 行的每一行包含四个整数 \(x_1\ y_1\ x_2\ y_2\) ，表示一个居民的起始位置 \((x_1 ,y_1)\) 和结束位置 \((x_2 ,y_2)\)。

【输出格式】

　　输出 \(N\) 个整数，为每个居民行走的距离。

【输入输出样例】

　InMut

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

　OutMut

6
5
5
4
4

【输入输出样例解释】

　　第一个居民可以逆时针走：(0,0)→(2,0)→(2,2)→(0,2)→(0,2)。
　　第二个居民可以顺时针走： (0,2)→(2,2)→(2,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：\)没有额外限制。

【来源】

　　Mr.he