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]$$$.

Input

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.

Output

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

Note

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

Closest Pair

Examples