$$$OX$$$ 轴上有 $$$n$$$ 个加权点。第 $$$i$$$ 个点的坐标和权重分别为 $$$x_i$$$ 和 $$$w_i$$$。所有点都有不同的坐标和正权重。此外,$$$x_i < x_{i + 1}$$$ 对于任何 $$$1 \leq i < n$$$ 成立。
第 $$$i$$$ 个点和第 $$$j$$$ 个点之间的加权距离定义为 $$$|x_i - x_j| \cdot (w_i + w_j)$$$,其中 $$$|val|$$$ 表示 $$$val$$$ 的绝对值。
您应该回答 $$$q$$$ 查询,其中第 $$$i$$$ 查询要求以下内容:查找子数组 $$$[l_i,r_i]$$$ 中的点中所有不同点对之间的最小加权距离。
输入
第一行包含 2 个整数 $$$n$$$ 和 $$$q$$$ $$$(2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5)$$$ — 点数和查询数。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$w_i$$$ $$$(-10^9 \leq x_i \leq 10^9; 1 \leq w_i \leq 10^9)$$$ — 坐标和权重第 $$$i$$$ 个点。
保证分数按 $$$x$$$ 的升序给出。
然后是 $$$q$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \leq l_i < r_i \leq n)$$$ — 第 $$$i$$$ 查询的给定子数组。
输出
对于每个查询输出一个整数,给定子数组中所有一对不同点之间的最小加权距离。
示例
输入 #1
5 5 -2 2 0 10 1 1 9 2 12 7 1 3 2 3 1 5 3 5 2 4
输出 #1
9 11 9 24 11
注意
对于第一个查询,最小加权距离位于点 $$$1$$$ 和 $$$3$$$ 之间,等于 $$$|x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9$$$。
对于第二个查询,最小加权距离位于点 $$$2$$$ 和 $$$3$$$ 之间,等于 $$$|x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11$$$。
对于第四个查询,最小加权距离位于点 $$$3$$$ 和 $$$4$$$ 之间,等于 $$$|x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24$$$。