Teleporters

Anna and Beka are at different points on a coordinate line and want to meet. Their only way to move is by teleporters.

There are $N$ teleporters. The $i$-th one is located at coordinate $c_i$ and operates at frequency $f_i$. Only the teleporters with frequency in the range $[L, R]$ are available.

Using a teleporter takes one minute and moves the user to the reflection of their current coordinate across the teleporter's location. If the coordinate before use is $x_1$ and the coordinate after use is $x_2$, then $(x_1 + x_2) / 2 = c_i$.

Every minute, Anna and Beka must each use one of the available teleporters (not necessarily the same one). While they teleport, they feel discomfort equal to the absolute difference between the frequencies of the two teleporters they use. The travel difficulty is the maximum discomfort felt over the whole trip.

There are $Q$ scenarios. For each one, determine whether Anna and Beka can ever meet using the available teleporters. If they can, print the minimum possible travel difficulty. The total travel time does not affect the answer.

Each scenario is given by four integers:

• $A$: Anna's starting coordinate
• $B$: Beka's starting coordinate
• $L$: the minimum frequency of the available teleporters
• $R$: the maximum frequency of the available teleporters

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

The second line contains $N$ integers $c_1, c_2, \dots, c_N$.

The third line contains $N$ integers $f_1, f_2, \dots, f_N$.

Each of the following $Q$ lines contains four integers $A$, $B$, $L$, and $R$ describing one scenario. It is guaranteed that $A \ne B$.

Print $Q$ space-separated integers on a single line. The $j$-th integer is the answer for scenario $j$.

• $2 \le N \le 50000$
• $1 \le Q \le 50000$
• $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$