城市隔离

题目描述

浣熊市因突发事件实施了隔离政策，整条 $y=0$ 的道路被封锁成一道“隔离带”，任何人都不能随意跨越。不过，为了维持城市的基本运转，政府在隔离带上设置了 $n$ 个检查站，分别位于坐标 $(a_1,0),(a_2,0),\dots,(a_n,0)$。只有通过任意检查站，人们才能从城市的南部前往北部（$y>0$），或反之。

整个浣熊市可以被抽象成一个网格街区，每一步只能走到相邻的街区。若两个街区 $(x_1,y_1),(x_2,y_2)$ 满足 $|x_1-x_2|+|y_1-y_2|=1$，则称它们相邻。

现在有很多市民需要出行，你需要帮他们计算：在遵守隔离规则的前提下，从起点走到终点的最短距离。

输入格式

第一行包含两个正整数 $n,Q$，其中 $n$ 表示检查站的数量，$Q$ 表示需要出行的市民数量。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示坐标为 $(a_i,0)$ 的位置有检查站。

接下来 $Q$ 行，每行有 $4$ 个整数 $x_1,y_1,x_2,y_2$，表示一个居民要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$。

输出格式

输出 $Q$ 行，每行一个整数，表示相应居民出行的最短距离。

样例 #1

输入 #1

3 3
-1 10 1
1 1 3 1
-3 3 0 -4
8 2 8 -2

输出 #1

2
10
8

说明/提示

【数据范围】

• 对于 $20\%$ 的数据，所有输入数字的绝对值不超过 $100$；
• 对于 $40\%$ 的数据，$1\le n,Q\le 5000$；
• 对于 $100\%$ 的数据，$1\le n,Q\le 5\times 10^5$，所有输入数字的绝对值不超过 $10^9$，保证 $a_i$ 两两不同，保证所有询问中 $y_1,y_2\ne 0$。