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

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

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

입력 형식

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

둘째 줄부터 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까지 허용한다.

예제 입력

4 2
1 4
2 3
0 1
1 1
1 4
3 4

예제 출력

5.0000000
1.0000000

힌트

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