A14767 | 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 < x_{i + 1}$ holds for any $1 \leq i < 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]$ .

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 < r_i \leq n)$ — the given subarray of the $i$ -th query.

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