Problem Description

Xiao C has a huge pond where many lotus flowers are planted. In summer, many large lotus seedpods grow in the pond.

To understand how the seedpods grow, Xiao C measured the position of each seedpod. Each seedpod corresponds to a coordinate $(x, y)$ in the 2D Cartesian coordinate system. These coordinates form a sequence, denoted as $\mathbf{A}$, where $A_i$ represents the coordinate of the $i$-th seedpod.

Xiao C plans to use magic to collect some of the seedpods. Because his power is limited, he can only collect all seedpods in an interval $[l, r]$ of the sequence $\mathbf{A}$. The energy required for one collection is the sum of the Manhattan distances between every pair of seedpods in that interval (where $dist(a,b) = |x_a - x_b| + |y_a - y_b|$).

Now Xiao C gives you multiple collection plans $[l, r]$ and hopes you can help compute the energy needed to collect the seedpods in each interval. (Each plan is independent.)

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of seedpods and the number of queries.

The next $n$ lines each contain two integers $x_i$ and $y_i$, representing the $x$- and $y$-coordinates of the $i$-th seedpod $A_i$ in the sequence.

The next $m$ lines each contain two integers $l_i$ and $r_i$, representing the left and right endpoints of the interval to be collected in this query (the interval includes endpoints).

Output Format

Output $m$ lines. The $i$-th line outputs one integer, representing the answer to the $i$-th query.

5 3
1 1
3 3
2 2
1 3
3 1
2 2
2 4
1 5

0
6
24

Hint

Sample Explanation

For the first query: there is only one seedpod.

For the second query:

• $dist[(3,3), (2,2)] = 2$
• $dist[(3,3), (1,3)] = 2$
• $dist[(2,2), (1,3)] = 2$

For the third query:

• $dist[(1,1), (3,3)] = 4$
• $dist[(1,1), (2,2)] = 2$
• $dist[(1,1), (1,2)] = 2$
• $dist[(1,1), (3,1)] = 2$
• $dist[(3,3), (2,2)] = 2$
• $dist[(3,3), (1,2)] = 2$
• $dist[(2,2), (1,2)] = 2$
• $dist[(2,2), (3,1)] = 2$
• $dist[(1,3), (3,1)] = 4$

Constraints

For $10\%$ of the testdata, $1 \le n, m \le 10$, $|x_i|, |y_i| \le 10$.

For $20\%$ of the testdata, $1 \le n, m \le 1000$, $|x_i|, |y_i| \le 10^3$.

For $40\%$ of the testdata, $1 \le n \le 5000$, $1 \le m \le 10^5$, $|x_i|, |y_i| \le 10^5$.

For another $10\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5000$, $|x_i|, |y_i| \le 10^5$.

For all testdata, $1 \le n, m \le 100000$, $0 \le |x_i|, |y_i| \le 10^8$, $1 \le l \le r \le n$. There may be two seedpods with the same coordinates. The testdata scale has multiple levels.

Translated by ChatGPT 5