Teleporters

Anna and Beka are at different points on a coordinate line, planning to meet. Their only means of movement is through the use of teleporters.

There are $N$ teleporters, with the $i$-th teleporter located at coordinate $c[i]$ and operating at a frequency denoted as $f[i]$. However, not all of them are currently available; only those within the frequency range $[L,R]$ can be used.

Using a teleporter takes a minute and transports its user to a coordinate that is a reflection of the original coordinate around the teleporters location. In other words, if the original coordinate was $x_1$, then after using teleporter $i$, the resulting coordinate $x_2$ will satisfy the equation $(x_1 + x_2 )/2 = c[i]$.

Each minute, Anna and Beka must use one of the available teleporters (not necessarily different ones). They will communicate during teleportation and experience discomfort equal to the absolute difference of the frequencies of the teleporters they are using. The overall difficulty of the travel is defined as the maximum discomfort they have experienced.

You will be asked about $Q$ different scenarios, and for each one, your task is to determine whether Anna and Beka can ever meet using available teleporters, and if so, what the minimum possible travel difficulty is.

A single scenario is described 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

For each scenario, print the minimum travel difficulty if they can meet and $-1$ otherwise. Please note that the total travel time is irrelevant for the purposes of this task.

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 describes one scenario with four integers: $A$, $B$, $L$ and $R$ ($A \ne B$).

Print $Q$ space-separated integers in a single line: answers to the scenarios $1$, $2$, $\dots$ ,$Q$.

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