Anna 和 Beka 位于坐标轴上的不同点，计划会合。他们唯一的移动方式是使用传送器。

共有 $N$ 个传送器，第 $i$ 个传送器位于坐标 $c[i]$，其工作频率记为 $f[i]$。然而，并非所有传送器当前都可用；只有频率在范围 $[L, R]$ 内的传送器可以使用。

使用传送器需要一分钟，并将使用者传送到关于传送器位置对称的坐标点。换句话说，如果原始坐标为 $x_1$，那么在使用传送器 $i$ 后，得到的坐标 $x_2$ 将满足方程 $(x_1 + x_2)/2 = c[i]$。

每一分钟，Anna 和 Beka 必须使用一个可用的传送器（不一定是同一个）。他们在传送过程中进行交流，并承受等于他们所使用的传送器频率之差的绝对值的“不适感”。旅行的总难度定义为他们所经历的最大不适感。

你将面临 $Q$ 个不同的场景，对于每个场景，你的任务是确定 Anna 和 Beka 是否能够使用可用的传送器会合，如果可以，求出最小的旅行难度。

单个场景由四个整数描述： $A$：Anna 的起始坐标 $B$：Beka 的起始坐标 $L$：可用传送器的最小频率 $R$：可用传送器的最大频率

对于每个场景，如果他们能会合，请输出最小旅行难度，否则输出 $-1$。请注意，总旅行时间与本题无关。

输入格式

第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $N$ 个整数：$c[1], c[2], \dots, c[N]$。 第三行包含 $N$ 个整数：$f[1], f[2], \dots, f[N]$。 接下来的 $Q$ 行，每行描述一个场景，包含四个整数：$A, B, L$ 和 $R$ ($A \neq B$)。

输出格式

在一行中输出 $Q$ 个空格分隔的整数，分别对应场景 $1, 2, \dots, Q$ 的答案。

样例

样例输入 1

4 3
4 6 8 10
7 1 9 4
3 11 1 50
3 11 1 5
5 7 1 1

样例输出 1

2 3 -1

说明

在第一个场景中，如果 Anna 使用传送器 2，Beka 使用传送器 4，他们将在坐标 9 会合，不适感为 $|1 - 4| = 3$。 更好的方案是 Anna 使用传送器 1，Beka 使用传送器 3；在这种情况下，他们在 $F = 5$ 处会合，不适感为 $|7 - 9| = 2$。 在第二个场景中，由于频率范围的限制，更好的方案不再可用。 在第三个场景中，只有一个可用的传送器，无法会合。

样例输入 2

3 3
-2 1 -1
10 1 3
-6 6 20 20
-6 6 0 20
-6 6 2 20

样例输出 2

-1 2 7

坐标可以是负数。

数据范围

• $2 \le N \le 50\,000$
• $1 \le Q \le 50\,000$
• $1 \le f[i] \le 10^9$
• $-10^9 \le c[i], A, B \le 10^9$
• $1 \le L \le R \le 10^9$

子任务

1. (11 分) $N, Q \le 10$; $|c[i]|, f[i] \le 50$。
2. (10 分) $N \le 100$; $L = 1; R = 10^9$; $|c[i]|, f[i] \le 100$。
3. (5 分) $N = 2; L = 1; R = 10^9$。
4. (9 分) $N \le 1\,000; L = 1; R = 10^9$; $f[i] = 1$。
5. (6 分) $L = 1; R = 10^9$; $f[i] = 1$。
6. (7 分) $N \le 1\,000; L = 1; R = 10^9$。
7. (17 分) $L = 1; R = 10^9$。
8. (8 分) $L = 1$。
9. (14 分) $N, Q \le 20\,000$。
10. (13 分) 无附加限制。

Figure 1. Anna 和 Beka 的传送过程示意图