인경산

인하대학교 뒤쪽에는 2차원 평면 위의 산인 인경산이 있다. 인경산에는 여러 산장이 있고, 인접한 두 산장 사이에는 직선 등산 코스가 있다. 민겸이는 등산을 좋아해 인경산에서 산장과 산장 사이를 오가며 물건을 배달하는 아르바이트를 한다.

민겸이는 아르바이트를 하면서 어떤 산장에서 다른 산장으로 이동할 때 오르막길, 내리막길, 평지에서의 체력 소모가 다르다는 것을 알았다. 민겸이는 오르막길을 지날 때는 거리의 3배만큼, 평지를 지날 때는 거리의 2배만큼, 내리막길을 지날 때는 거리만큼 체력을 소모한다.

다음 질의를 해결하는 프로그램을 작성하시오.

• i j: i번 산장에서 출발해 j번 산장까지 이동하는 데 드는 체력 소모량의 최솟값을 출력한다.

첫째 줄에는 산장의 개수 $N$과 질의의 개수 $Q$가 주어진다.

둘째 줄에는 각 산장의 $x$ 좌표가 양의 정수로 주어진다.

셋째 줄에는 각 산장의 $y$ 좌표가 양의 정수로 주어진다.

이때, 각 산장은 $x$ 좌표가 오름차순이 되도록 정렬된 순서대로 주어진다.

다음 $Q$개의 줄에 걸쳐 질의에 해당하는 두 양의 정수 $i$, $j$가 주어진다. 산장의 번호는 1부터 $N$까지이다.

$Q$개의 줄에 걸쳐 각 질의의 정답을 출력한다.

정답과의 절대오차 또는 상대오차가 $10^{-4}$ 이하이면 정답으로 인정한다.

• $2 \le N \le 200,000$
• $1 \le Q \le 200,000$
• $1 \le x$ 좌표 $\le 10^9$, $1 \le y$ 좌표 $\le 10^9$
• $1 \le i, j \le N$
• $i \ne j$
• 각 산장의 $x$ 좌표는 모두 다르다.