Задана бесконечная клеточная полоса. На ней расположены $$$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$$$. Вы можете двигать ящики в любом порядке любое количество раз.

Веса некоторых ящиков иногда изменяются, поэтому Вам необходимо обработать запросы двух видов:

1. $$$id$$$ $$$nw$$$ — вес $$$w_{id}$$$ ящика $$$id$$$ становится равным $$$nw$$$.
2. $$$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$$$.