Gather at one point

$N$ people stand on a two dimensional plane. The people are numbered from 1 to $N$.

The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $\max(|x_1 - x_2|, |y_1 - y_2|)$.

Write a program that answers the following query.

• l r: person $l$ through person $r$ gather at a single point $P$ on the plane. Print the minimum possible sum of the distances between each of those people and $P$.

The point $P$ can be anywhere on the plane, and its coordinates do not have to be integers.

The first line contains the number of people $N$ and the number of queries $Q$, separated by a space. ($1 \le N, Q \le 100\,000$)

Each of the next $N$ lines contains the coordinates $X_i$ and $Y_i$ of person $i$, separated by a space. ($-1\,000\,000\,000 \le X_i, Y_i \le 1\,000\,000\,000$)

Each of the next $Q$ lines contains $L_i$ and $R_i$ of a query, separated by a space. ($1 \le L_i \le R_i \le N$)

Print the answer to each query on its own line, in the order the queries are given.

The answer is always a multiple of $0.5$, so print it with exactly one digit after the decimal point. Print 5.0 for an answer of $5$ and 8.5 for an answer of $8.5$.

In the first example, the first query is minimized by gathering at $(1.5, 2.5)$, and the second query is minimized by gathering at $(1, 1)$.