题目描述

可爱小苹果 和 黑黑布莱克 在数轴上的两个不同的点 $A,B$，他们想要见面，但是他们只能通过传送器移动。

有 $N$ 个传送器，第 $i$ 个位于坐标轴 $c_i$ 位置，频率为 $f_i$。由于某种原因，只有频率 $\in[L,R]$ 的传送器可以使用。

使用一个传送器会将一个人传送到与其坐标对称的点。形式化地说，一个人传送前后的位置 $x_1,x_2$ 与传送器的位置 $c_i$ 满足 $\frac{x_1+x_2}{2}=c_i$。

可爱小苹果 和 黑黑布莱克 会不断同时各自选择一个传送器 $p,q$（不需要相同），进行传送并经历 $|f_p-f_q|$ 的疲劳值，直到他们抵达同一位置。整个过程的疲劳值为每次经历的疲劳值的最大值。

给定 $Q$ 次询问，每次给定一组 $[L,R]$，求 可爱小苹果 和 黑黑布莱克 见面的总疲劳值的最小值，或报告他们不可能通过这些传送器见面。

输入格式

第一行输入两个整数 $N,Q$。

第二行输入 $N$ 个整数 $c_i$。

第三行输入 $N$ 个整数 $f_i$。

接下来 $Q$ 行，每行输入四个整数 $A,B,L,R$，保证 $A\neq B$。

输出格式

输出一行 $Q$ 个整数，代表每个询问总疲劳值的最小值。特别地，如果不可能见面，输出 -1。

输入输出样例 1

输入输出样例 2

输入输出样例 3

满足子任务 1 的限制。

输入输出样例 4

满足子任务 2 的限制。

输入输出样例 5

满足子任务 7 的限制。

输入输出样例 6

满足子任务 9 的限制。

输入输出样例 7

满足子任务 10 的限制。

说明/提示

下面为第一组样例的解释。

第一次询问中，如果 可爱小苹果选择第二个传送器， 黑黑布莱克 选择第四个传送器，可以在 $9$ 处见面，疲劳值为 $3$。但如果 可爱小苹果选择第一个传送器， 黑黑布莱克选择第三个传送器，可以在 $5$ 处见面，疲劳值为 $2$。

第二次询问中，上述的第二种方法由于 $[L,R]$ 的限制不合法。

第三次询问中，只有一个可用的传送器，见面是不可能的。

注意坐标可能是负数。

数据规模与约定

对于 $100\%$ 的数据，保证 $2\leq N\leq 5\times 10^4$，$1\leq Q\leq 5\times 10^4$，$1\leq f_i\leq 10^9$，$-10^9\leq c_i,A,B\leq 10^9$，$1\leq L\leq R\leq 10^9$。