CF1635F.Closest Pair

There are $n$ weighted points on the $OX$-axis. The coordinate and the weight of the $i$-th point is $x_i$ and $w_i$, respectively. All points have distinct coordinates and positive weights. Also, $x_i \lt x_{i + 1}$ holds for any $1 \leq i \lt n$.

The weighted distance between $i$-th point and $j$-th point is defined as $|x_i - x_j| \cdot (w_i + w_j)$, where $|val|$ denotes the absolute value of $val$.

You should answer $q$ queries, where the $i$-th query asks the following: Find the minimum weighted distance among all pairs of distinct points among the points in subarray $[l_i,r_i]$.

在 $OX$ 轴上有 $n$ 个带权点。第 $i$ 个点的坐标和权重分别为 $x_i$ 和 $w_i$。所有点的坐标互不相同，且权重均为正数；此外，对任意 $1 \leq i < n$，均满足 $x_i < x_{i + 1}$。

第 $i$ 个点与第 $j$ 个点之间的加权距离定义为 $|x_i - x_j| \cdot (w_i + w_j)$，其中 $|val|$ 表示 $val$ 的绝对值。

你需要回答 $q$ 个查询，其中第 $i$ 个查询要求：在子数组 $[l_i, r_i]$ 所包含的点中，求所有不同点对之间的最小加权距离。

The first line contains 2 integers $n$ and $q$ $(2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5)$ — the number of points and the number of queries.

Then, $n$ lines follows, the $i$-th of them contains two integers $x_i$ and $w_i$ $(-10^9 \leq x_i \leq 10^9; 1 \leq w_i \leq 10^9)$ — the coordinate and the weight of the $i$-th point.

It is guaranteed that the points are given in the increasing order of $x$.

Then, $q$ lines follows, the $i$-th of them contains two integers $l_i$ and $r_i$ $(1 \leq l_i \lt r_i \leq n)$ — the given subarray of the $i$-th query.

第一行包含两个整数 $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 \lt r_i \leq n$）—— 表示第 $i$ 次查询所给定的子数组范围。

For each query output one integer, the minimum weighted distance among all pair of distinct points in the given subarray.

对于每个查询，输出一个整数，表示给定子数组中所有不同点对的最小加权距离。

For the first query, the minimum weighted distance is between points $1$ and $3$, which is equal to $|x_1 - x_3| \cdot (w_1 + w_3) = |-2 - 1| \cdot (2 + 1) = 9$.

For the second query, the minimum weighted distance is between points $2$ and $3$, which is equal to $|x_2 - x_3| \cdot (w_2 + w_3) = |0 - 1| \cdot (10 + 1) = 11$.

For the fourth query, the minimum weighted distance is between points $3$ and $4$, which is equal to $|x_3 - x_4| \cdot (w_3 + w_4) = |1 - 9| \cdot (1 + 2) = 24$.

对于第一个查询，最小加权距离出现在点 $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$。