25711번 - 인경산 스페셜 저지

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

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

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

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

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

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

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

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

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

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

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

• 2 ≤ N ≤ 200,000
• 1 ≤ Q ≤ 200,000
• 1 ≤ x 좌표, y 좌표 ≤ 10⁹
• 1 ≤ i, j ≤ N
• ​​i ≠ j 
• 각 산장의 x 좌표는 모두 다르다.