В Candyland есть парк сладостей, в котором есть не только красивые пейзажи и увлекательные аттракционы, но и множество пунктов бесплатной раздачи конфет, что привлекает множество детей-сладкоежек.

Структура парка сладостей весьма необычна: он состоит из $n$ достопримечательностей, в каждой из которых есть пункт выдачи конфет. Пронумеруем достопримечательности от $1$ до $n$. Эти достопримечательности соединены $n - 1$ двунаправленными дорогами, и весь парк является связным, то есть из любой достопримечательности можно добраться до любой другой по этим дорогам.

В парке представлено большое разнообразие видов конфет — всего $m$ видов, пронумерованных от $1$ до $m$. Каждый пункт выдачи раздает только конфеты определенного вида; обозначим вид конфет в достопримечательности $i$ как $C_i$.

Посетители парка не любят ходить по пройденному пути, поэтому они всегда перемещаются из одной конкретной достопримечательности в другую по единственному кратчайшему пути. Проходя через каждую достопримечательность, они пробуют одну конфету соответствующего вида.

У каждого вида конфет есть свой уровень «вкусности». Согласно оценкам посетителей, вкусность конфеты $i$-го вида равна $V_i$. Кроме того, если посетитель пробует конфеты одного и того же вида несколько раз, он начинает чувствовать пресыщение. Согласно статистике, «индекс новизны» $i$-го по счету употребления конфеты определенного вида равен $W_i$. Если посетитель пробует конфету $j$-го вида в $i$-й раз, его индекс удовольствия $H$ увеличивается на произведение вкусности и индекса новизны, то есть на $V_j W_i$. Итоговый индекс удовольствия посетителя от прогулки по парку равен сумме этих произведений.

Разумеется, виды конфет, выдаваемые в каждом пункте, не всегда остаются неизменными. Иногда вид конфет в некоторых пунктах может меняться (на любой из $m$ видов), чтобы посетители всегда чувствовали новизну.

Сотрудник парка, маленький А, получил задание рассчитывать индекс удовольствия каждого посетителя на основе последних данных парка. Однако маленький А, не сильный в математике, начинает чувствовать головокружение при виде множества цифр. Как лучший друг маленького А, вы решили помочь ему.

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

Первая строка содержит три целых положительных числа $n, m, q$, обозначающие количество достопримечательностей, количество видов конфет и количество операций соответственно.

Вторая строка содержит $m$ целых положительных чисел $V_1, V_2, \cdots, V_m$.

Третья строка содержит $n$ целых положительных чисел $W_1, W_2, \cdots, W_n$.

С четвертой по $(n + 2)$-ю строку содержатся по два целых положительных числа $A_i, B_i$, обозначающих наличие прямой дороги между этими достопримечательностями.

$(n + 3)$-я строка содержит $n$ целых положительных чисел $C_1, C_2, \dots, C_n$.

Далее следуют $q$ строк, каждая из которых содержит три целых числа $Type, x, y$, описывающих операцию:

Если $Type$ равен $0$, то $1 \leq x \leq n$, $1 \leq y \leq m$, что означает изменение вида конфет в достопримечательности $x$ на $y$.

Если $Type$ равен $1$, то $1 \leq x, y \leq n$, что означает запрос индекса удовольствия для пути от $x$ до $y$.

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

Для каждой операции с $Type = 1$ выведите ответ в отдельной строке в порядке поступления запросов.

Примеры

Пример 1

4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2

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

84
131
27
84

Ограничения

Для всех данных $1 \leq v_i, w_i \leq 10^6$, $1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq m$. Последовательность $w_1, w_2, \dots, w_n$ является невозрастающей, то есть для любого $1 < i \leq n$ выполняется $w_i \leq w_{i - 1}$.

Остальные ограничения приведены в таблице ниже: