P15839 [Lanqiao Cup 1st International Contest] Lotus Seedpod Pond

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.)

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 $m$ lines. The $i$-th line outputs one integer, representing the answer to the $i$-th query.

### 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