题目描述

整条 $y=0$ 的道路构成隔离带，只允许通过横坐标为 $a_1,a_2,\ldots,a_n$ 的检查站穿越隔离带。网格中每次只能沿上下左右走一格。对于每次询问，求从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 在遵守隔离规则时的最短步数。

输入格式

第一行两个正整数 $n,Q$。第二行 $n$ 个互不相同的整数 $a_i$，表示检查站 $(a_i,0)$。接下来 $Q$ 行，每行四个整数 $x_1,y_1,x_2,y_2$。

输出格式

每次询问输出一行一个整数，表示最短距离。

样例 1

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

2
10
8

数据范围

$1\le n,Q\le5\times 10^5$，所有输入整数的绝对值不超过 $10^9$；检查站位置互异，所有询问 $y_1,y_2\ne0$。

注意： 若起点终点位于隔离带同一侧，可直接沿网格行走；不同侧时必须经过某个检查站。