说明

小 C 有一个巨大的池塘，池塘里种了许多荷花。到了夏天，池塘里长出了许多巨大的莲蓬。

为了了解莲蓬的生长情况，小 C 测量了每个莲蓬的位置，每个莲蓬位置对应了平面直角坐标系中的一个坐标 $(x, y)$。这些莲蓬的坐标构成了一个序列，记为 $\mathbf{A}$，其中 $A_i$ 表示第 $i$ 个莲蓬的坐标。

小 C 打算使用魔法采集部分莲蓬，由于小 C 的功力有限，他只能采集序列 $\mathbf{A}$ 中一个区间 $[l, r]$ 的所有莲蓬。这次采集需要消耗的能量为该区间中每两个莲蓬的曼哈顿距离（$dist(a,b) = |x_a - x_b| + |y_a - y_b|$）之和。

现在小 C 给了你多个采集计划 $[l, r]$，希望你能帮他求出采集每个区间的莲蓬所消耗的能量。（采集计划之间独立）

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$，分别表示莲蓬的数量和询问的个数。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，分别表示序列中第 $i$ 个莲蓬 $A_i$ 的横、纵坐标。

接下来 $m$ 行，其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，分别表示这次询问所采集的莲蓬区间的左右端点（区间包括端点）。

输出格式

输出 $m$ 行，其中第 $i$ 行输出一个整数，表示第 $i$ 组询问的答案。

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

0
6
24

提示

样例说明

对于第一个询问：只有一个莲蓬。

对于第二个询问：

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

对于第三个询问：

• $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$

评测用例规模与约定

对于 $10\%$ 的评测用例，$1 \le n, m \le 10$，$|x_i|, |y_i| \le 10$；

对于 $20\%$ 的评测用例，$1 \le n, m \le 1000$，$|x_i|, |y_i| \le 10^3$；

对于 $40\%$ 的评测用例，$1 \le n \le 5000$，$1 \le m \le 10^5$，$|x_i|, |y_i| \le 10^5$；

对于另外 $10\%$ 的评测用例，$1 \le n \le 10^5$，$1 \le m \le 5000$，$|x_i|, |y_i| \le 10^5$；

对于所有评测用例，$1 \le n, m \le 100000$，$0 \le |x_i|, |y_i| \le 10^8$，$1 \le l \le r \le n$，可能存在两个莲蓬的坐标相同，数据规模有一定梯度。