B. Космическая гавань
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \le m \le n \le 3 \cdot 10^5$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — количество точек, гаваней и запросов соответственно.

Вторая строка содержит $$$m$$$ различных целых чисел $$$X_1, X_2, \ldots, X_m(1 \le X_i \le n)$$$ — позиции $$$i$$$-й гавани.

Третья строка содержит $$$m$$$ целых чисел $$$V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$$$ — значения $$$i$$$-й гавани.

Каждая из следующих $$$q$$$ строк содержит три целых числа. Первое целое число $$$t$$$ ($$$1\le t \le 2$$$) — тип запроса. Если $$$t=1$$$, то следующие два целых числа $$$x$$$ и $$$v$$$ ($$$2 \le x \le n - 1$$$, $$$1 \le v \le 10^7$$$) — запрос первого типа. Если $$$t=2$$$, то следующие два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос второго типа.

Гарантируется, что есть хотя бы один запрос второго типа.

Выходные данные

Для каждого запроса второго типа выведите одно целое число в новой строке — ответ на этот запрос.

Пример
Входные данные
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8
Выходные данные
171
0
15
Примечание

Для первого запроса типа $$$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$$$ соответственно.