You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

喂小猪

时间限制：$2s$

空间限制：$256MB$

题目背景：

$piggy$是猪产大亨，因此，他需要每天去喂猪。

题目描述：

$piggy$的养殖场可以看作是一个$X*Y$二维平面。在养殖场上有$n$个仓库，每个仓库里面都有好多好多猪饲料。

$piggy$有$m$个计划，每个计划给出了$piggy$所在坐标$(x_1,y_1)$和目标猪棚坐标$(x_2,y_2)$，表示从$(x_1,y_1)$走到$(x_2,y_2)$，并且至少经过一个仓库。

不幸的是，$piggy$的车是笨笨车，只能向右和向下走，每向左一步或者向上一步就要花$1$个猪猪币，使其在走这一步的时候成为聪明车。

为了省钱，$piggy$希望你能告诉他每个计划最少需要多少个猪猪币。

输入描述：

第一行两个整数，表示n和m
第二行到第n+1行，每行两个正整数，表示仓库坐标
第n+2行到第n+m+1行，每行四个正整数，x1,y1,x2,y2；表示起点坐标(x1,y1)和终点坐标(x2,y2)

输出描述：

共m行，每行一个整数，表示最少猪猪币

样例输入：

2 3
2 5
5 3
3 2 5 3
3 2 4 4
2 3 3 3

样例输出：

0
1
2

数据范围：

$20pts：X，Y，n，m \leq 20$

$50pts:X,Y,n,m\leq 200$

$100pts:X,Y \leq 500;n,m\leq 10^5$