모여라

2차원 평면에 $N$명이 서 있다. 사람에게는 1번부터 $N$번까지 번호가 붙어 있다.

두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $\max(|x_1 - x_2|, |y_1 - y_2|)$로 정의한다.

다음 쿼리를 처리하는 프로그램을 작성하시오.

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

점 $P$는 평면 위의 어느 곳이든 될 수 있고, 좌표가 정수일 필요는 없다.

첫째 줄에 사람의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\,000$)

둘째 줄부터 $N$개의 줄에 $i$번 사람의 좌표 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. ($-1\,000\,000\,000 \le X_i, Y_i \le 1\,000\,000\,000$)

다음 $Q$개의 줄에 쿼리의 $L_i$와 $R_i$가 공백으로 구분되어 주어진다. ($1 \le L_i \le R_i \le N$)

각 쿼리의 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.

답은 항상 $0.5$의 배수이므로 소수점 아래 한 자리까지 정확히 출력한다. 답이 $5$이면 5.0을, $8.5$이면 8.5를 출력한다.

첫 번째 예제의 첫 번째 쿼리는 $(1.5, 2.5)$에 모일 때가 최소이고, 두 번째 쿼리는 $(1, 1)$에 모일 때가 최소이다.