텔레포터

안나와 베카는 좌표축 위의 서로 다른 지점에 있고, 만나려고 한다. 두 사람이 이동할 수 있는 방법은 텔레포터뿐이다.

텔레포터는 $N$개 있다. $i$번째 텔레포터는 좌표 $c_i$에 있고, 주파수 $f_i$로 동작한다. 주파수가 $[L, R]$ 범위에 있는 텔레포터만 사용할 수 있다.

텔레포터를 한 번 사용하는 데 1분이 걸리며, 사용자는 현재 좌표를 텔레포터 위치를 기준으로 대칭인 좌표로 옮겨 간다. 사용 전 좌표를 $x_1$, 사용 후 좌표를 $x_2$라고 하면 $(x_1 + x_2) / 2 = c_i$가 성립한다.

매 분 안나와 베카는 사용 가능한 텔레포터 중 하나씩을 반드시 사용해야 한다(같은 텔레포터를 써도 되고 달라도 된다). 텔레포터를 쓰는 동안 두 사람은 각자 사용한 텔레포터 주파수 차이의 절댓값만큼 불편함을 느낀다. 이동 난이도는 전체 이동 중 느낀 불편함의 최댓값으로 정의한다.

$Q$개의 시나리오가 주어진다. 각 시나리오마다 사용 가능한 텔레포터로 두 사람이 만날 수 있는지 판단하고, 만날 수 있다면 가능한 이동 난이도의 최솟값을 출력한다. 전체 이동 시간은 답과 무관하다.

각 시나리오는 네 정수로 주어진다.

• $A$: 안나의 시작 좌표
• $B$: 베카의 시작 좌표
• $L$: 사용 가능한 텔레포터의 최소 주파수
• $R$: 사용 가능한 텔레포터의 최대 주파수

첫째 줄에 두 정수 $N$과 $Q$가 주어진다.

둘째 줄에 $N$개의 정수 $c_1, c_2, \dots, c_N$이 주어진다.

셋째 줄에 $N$개의 정수 $f_1, f_2, \dots, f_N$이 주어진다.

이어지는 $Q$개의 줄에는 각각 한 시나리오를 나타내는 네 정수 $A$, $B$, $L$, $R$이 주어진다. $A \ne B$이다.

$Q$개의 정수를 공백으로 구분하여 한 줄에 출력한다. $j$번째 정수는 $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$