14895번 - 모여라 스페셜 저지

문제

N명의 사람들이 2차원 평면 위에 서있다. 사람의 번호는 1번부터 N번까지 번호가 매겨져 있다. 이때, 다음 쿼리의 정답을 구하는 프로그램을 작성하시오.

• l r: l번 사람부터 r번 사람까지 한 점 P에 모일 때, 각 사람과 점 P사이의 거리의 합의 최솟값을 출력한다.

두 점 (x₁, y₁), (x₂, y₂) 사이의 거리는 max(|x₁-x₂|, |y₁-y₂|)로 구한다.

입력

첫째 줄에 사람의 수 N과 쿼리의 수 Q (1 ≤ N, Q ≤ 100,000)

둘째 줄부터 N개의 줄에 사람의 좌표 X_i, Y_i가 공백으로 구분해서 주어진다. (-1,000,000,000 ≤ X_i, Y_i ≤ 1,000,000,000)

다음 Q개의 줄에는 쿼리 L_i, R_i가 공백으로 구분해서 주어진다. (1 ≤ L_i ≤ R_i ≤ N)

출력

각각의 쿼리마다 정답을 출력한다. 정답과의 절대/상대 오차는 10^-3까지 허용한다.

제한

힌트

첫 번째 쿼리의 경우에는 (1.5, 2.5)에 모이는 것이 최소이고, 두 번째 쿼리의 경우에는 (1, 1)에 모이는 것이 최소이다.