John Doe 发明了一种衡量两个不同长度数组之间距离的好方法。设第一个数组为 $a_1, \dots, a_{l_1}$，第二个数组为 $b_1, \dots, b_{l_2}$，则它们的距离定义为 $d(a, b) = \sum_{i=1}^{l_1} \sum_{j=1}^{l_2} |a_i - b_j|$。遗憾的是，该距离函数不满足三角不等式，但 John 还是决定进行一些实验。

John 有一个很大的数组 $a_1, \dots, a_n$。对于 $q$ 组参数 $(l_1, r_1, l_2, r_2)$，他想知道 $d((a_{l_1}, a_{l_1+1}, \dots, a_{r_1}), (a_{l_2}, a_{l_2+1}, \dots, a_{r_2}))$ 的值。请帮助他计算这些值。

输入格式

第一行包含两个整数 $n$ 和 $q$：数组中元素的数量和查询的数量（$1 \le n, q \le 10^5$）。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$：John 的大数组中的元素（$0 \le a_i \le 10^8$）。 接下来的 $q$ 行，每行包含四个整数 $l_1, r_1, l_2, r_2$，表示相应查询的参数（$1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$）。

输出格式

对于每个查询，在单独的一行中输出 $d((a_{l_1}, a_{l_1+1}, \dots, a_{r_1}), (a_{l_2}, a_{l_2+1}, \dots, a_{r_2}))$ 的值。

样例

输入 1

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

输出 1

1
3
6
4
40