На прямой линии расположены \(n\) точек, пронумерованных от \(1\) до \(n\). Изначально существует \(m\) гаваней, причем \(i\)-я гавань находится в точке \(X_i\) и имеет значение \(V_i\). Гарантируется, что в точках \(1\) и \(n\) существуют гавани. На каждой из \(n\) точек находится ровно один корабль. Стоимость перемещения корабля с его текущего местоположения до следующей гавани равна произведению значения ближайшей гавани слева и расстояния до ближайшей гавани справа. В частности, если корабль уже находится в гавани, стоимость перемещения его до следующей гавани равна \(0\).
Кроме того, имеется \(q\) запросов, каждый из которых является одним из \(2\) типов:
- \(1\) \(x\) \(v\) — Добавить гавань в точке \(x\) со значением \(v\). Гарантируется, что перед добавлением в точке \(x\) там еще нет гавани.
- \(2\) \(l\) \(r\) — Вывести сумму стоимости перемещения всех кораблей с точек от \(l\) до \(r\) до их следующих гаваней. Обратите внимание, что вам нужно только вычислить стоимость перемещения кораблей, но не перемещать их фактически.
Выходные данные
Для каждого запроса второго типа выведите одно целое число в новой строке — ответ на этот запрос.
Примечание
Для первого запроса типа \(2\), цена для кораблей на позициях \(2\), \(3\), \(4\) и \(5\) будет \(3(3 \times 1)\), \(0\), \(96(24 \times 4)\) и \(72(24 \times 3)\) соответственно.
Для второго запроса типа \(2\), так как корабль в точке \(5\) уже находится в гавани, ответ будет \(0\).
Для третьего запроса типа \(2\), цена для кораблей на позициях \(7\) и \(8\) будет \(15(15 \times 1)\) и \(0\) соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8
|
171
0
15
|