На оси \(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]\).
Выходные данные
Для каждого запроса выведите одно целое число — минимальное взвешенное расстояние среди всех пар различных точек в данном подмассиве.
Примечание
Для первого запроса минимальное взвешенное расстояние находится между точками \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
-2 2
0 10
1 1
9 2
12 7
1 3
2 3
1 5
3 5
2 4
|
9
11
9
24
11
|