$1s512MB$
题目描述
东云研究所的博士又在研发新玩意儿啦！这一次她发明了 $n$ 个投影机，第 $i$ 个投影机位于坐标 $c_i$ ，功率为 $f_i$ 。
使用一次投影机需要 $1s$，并且会将用户投影到关于投影机的对称位置。即若当前坐标为 $x$ ，那么使用第 $i$ 个投影机后坐标将会变成 $2c_i-x$ 。
博士和名乃现在分别位于 $x,y$ 两位置，为了测试投影机，她们想要经过若干次操作后使得两人在同一坐标上。
为了简化实验，博士事先规定双方每秒必须分别使用一个传送器（可以是同一个）。而在传送过程中由于两机器的功率不同会导致实验不稳定。定义一次操作的不稳定值为博士和名乃使用的投影机的功率之差的绝对值，本次实验的不稳定值为某一次操作中最大的不稳定值。
博士为了更好地测试性能，需要进行 $q$ 次实验。对于每次实验请输出最小的不稳定值，或者输出 $-1$ 表示两人无法相遇。注意，不需要最小化时间！
输入格式
第一行两个整数 $n,q$。
第二行 $n$ 个整数 $c_i$ 。
第三行 $n$ 个整数 $f_i$ 。
接下来 $q$ 行，每行四个整数 $x,y,l,r$ 表示询问博士初始在 $x$ ，名乃初始在 $y$ ，实验中只能启用功率在 $[l,r]$ 中的投影机的情况下，最小不稳定值是多少。如果两人不能相遇则输出 $-1$ 。
输出格式
输出一行 $q$ 个整数表示答案
样例 1~10
见下发样例 $\rm lab/ex\_lab1.in\sim lab/ex\_lab10.in$ 和 $\rm lab/ex\_lab1.out\sim \rm lab/ex\_lab10.out$。
分别满足子任务 $1\sim 10$。
数据范围
保证对于所有数据满足：$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,x,y\leq 10^9,1\leq l\leq r\leq 10^9$ 且 $x\not=y$。
$\rm subtask1\ 10pts:$ $n,q\leq 10,|c_i|,f_i\leq 50$。
$\rm subtask2\ 10pts:$ $n\leq 100,L=1,R=100,|c_i|,f_i\leq 100$
$\rm subtask3\ 5pts:$ $n=2,l=1,r=10^9$。
$\rm subtask4\ 10pts:$ $n\leq 1000,l=1,r=10^9,f_i=1$。
$\rm subtask5\ 5pts:$ $l=1,r=10^9,f_i=1$。
$\rm subtask6\ 5pts:$ $n\leq 1000,l=1,r=10^9$。
$\rm subtask7\ 15pts:$ $l=1,r=10^9$。
$\rm subtask8\ 10 pts:$ $l=1$。
$\rm subtask9\ 15pts:$ $n,q\leq 2\times 10^4$。
$\rm subtask10\ 15pts:$ 无限制。