Задана бесконечная клеточная полоса. На ней расположены \(n\) ящиков: \(i\)-й ящик находится в клетке \(a_i\) и имеет вес \(w_i\). Все \(a_i\) различны; также, \(a_{i - 1} < a_i\) для всех корректных \(i\).
Вы решили собрать вместе некоторые ящики. «Собрать вместе» ящики с номерами в отрезке \([l, r]\) означает, что вам необходимо их расположить таким образом, что их позиции образуют некоторый отрезок \([x, x + (r - l)]\).
За один шаг вы можете сдвинуть любой ящик в соседнюю клетку, если она не занята другим ящиком (т. е. выбрать \(i\) и изменить \(a_i\) на \(1\), при этом все позиции должны остаться различными). На передвижение ящика \(i\) на одну клетку вы тратите энергию, равную его весу \(w_i\). Вы можете двигать ящики в любом порядке любое количество раз.
Веса некоторых ящиков иногда изменяются, поэтому Вам необходимо обработать запросы двух видов:
- \(id\) \(nw\) — вес \(w_{id}\) ящика \(id\) становится равным \(nw\).
- \(l\) \(r\) — вы должны вычислить минимальную суммарную энергию, необходимую для того, чтобы собрать вместе ящики с номерами в отрезке \([l, r]\). Так как ответ может быть слишком большим, выведите остаток от деления ответа на \(1000\,000\,007 = 10^9 + 7\). Обратите внимание, при таком запросе ящики остаются на местах, вам нужно лишь вычислить ответ.
Обратите внимание, что минимизировать надо сам ответ, а не его остаток от деления на \(10^9 + 7\). Например, если у вас два возможных ответа — \(2 \cdot 10^9 + 13\) и \(2 \cdot 10^9 + 14\) — то необходимо выбрать первый ответ и вывести \(10^9 + 6\), даже с учетом того, что второй ответ дает остаток \(0\).
Выходные данные
Для каждого запроса второго типа выведите ответ на него в отдельной строке. Так как ответ может быть слишком большим, выведите остаток от деления его на \(1000\,000\,007 = 10^9 + 7\).
Примечание
Рассмотрим запросы из примера:
- \(1\ 1\): ящик только один, поэтому двигать его не надо.
- \(1\ 5\): мы можем сдвинуть ящики в отрезок \([4, 8]\): \(1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10\).
- \(1\ 3\): мы можем сдвинуть ящики в отрезок \([1, 3]\).
- \(3\ 5\): мы можем сдвинуть ящики в отрезок \([7, 9]\).
- \(-3\ 5\): изменение \(w_3\) из \(1\) в \(5\).
- \(-1\ 10\): изменение \(w_1\) из \(1\) в \(10\). Теперь веса ящиков равны \(w = [10, 1, 5, 1, 2]\).
- \(1\ 4\): мы можем сдвинуть ящики в отрезок \([1, 4]\).
- \(2\ 5\): мы можем сдвинуть ящики в отрезок \([5, 8]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
1 2 6 7 10
1 1 1 1 2
1 1
1 5
1 3
3 5
-3 5
-1 10
1 4
2 5
|
0
10
3
4
18
7
|