Problem Description

dXqwq and Haitang are at two different points $A, B$ on the number line. They want to meet, but they can only move using teleporters.

There are $N$ teleporters. The $i$-th teleporter is located at position $c_i$ on the number line and has frequency $f_i$. For some reason, only teleporters with frequency $\in [L, R]$ can be used.

Using a teleporter will send a person to the point symmetric with respect to its coordinate. Formally, if a person's positions before and after teleportation are $x_1, x_2$, and the teleporter position is $c_i$, then $\frac{x_1 + x_2}{2} = c_i$.

dXqwq and Haitang will repeatedly simultaneously choose a teleporter $p, q$ (not necessarily the same), teleport, and incur fatigue of $|f_p - f_q|$, until they reach the same position. The total fatigue of the whole process is the maximum fatigue incurred in any single step.

Given $Q$ queries, each query provides an interval $[L, R]$. Find the minimum possible total fatigue for dXqwq and Haitang to meet, or report that it is impossible for them to meet using these teleporters.

Input Format

The first line contains two integers $N, Q$.

The second line contains $N$ integers $c_i$.

The third line contains $N$ integers $f_i$.

The next $Q$ lines each contain four integers $A, B, L, R$, and it is guaranteed that $A \neq B$.

Output Format

Output one line containing $Q$ integers, representing the minimum total fatigue for each query. In particular, if it is impossible for them to meet, output -1.

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

2 3 -1

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

-1 2 7

Hint

[Sample Explanation]

The following explains the first sample.

In the first query, if dXqwq chooses the second teleporter and Haitang chooses the fourth teleporter, they can meet at $9$, with fatigue $3$. But if dXqwq chooses the first teleporter and Haitang chooses the third teleporter, they can meet at $5$, with fatigue $2$.

In the second query, the second method above is invalid due to the restriction of $[L, R]$.

In the third query, there is only one available teleporter, so meeting is impossible.

Note that coordinates may be negative.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (11 pts): $N, Q \leq 10$, $|c_i|, f_i \leq 50$.
• Subtask 2 (10 pts): $N \leq 100$, $L = 1$, $R = 10^9$, $|c_i|, f_i \leq 100$.
• Subtask 3 (5 pts): $N = 2$, $L = 1$, $R = 10^9$.
• Subtask 4 (9 pts): $N \leq 10^3$, $L = 1$, $R = 10^9$, $f_i = 1$.
• Subtask 5 (6 pts): $L = 1$, $R = 10^9$, $f_i = 1$.
• Subtask 6 (7 pts): $N \leq 10^3$, $L = 1$, $R = 10^9$.
• Subtask 7 (17 pts): $L = 1$, $R = 10^9$.
• Subtask 8 (8 pts): $L = 1$.
• Subtask 9 (14 pts): $N, Q \leq 2 \times 10^4$.
• Subtask 10 (13 pts): No special constraints.

For $100\%$ of the data, it is guaranteed that $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$.

Translated by ChatGPT 5