$N$ вершин образуют дерево (неориентированный связный граф без циклов). Вершины пронумерованы от $1$ до $N$, рёбра — от $1$ до $N-1$. Вершины имеют веса.

Напишите программу, выполняющую следующие два типа запросов.

• 1 u v: найти максимальную сумму подотрезка (непрерывной подпоследовательности) на пути из $u$ в $v$ (подотрезок может быть пустым, поэтому ответ неотрицательный) и вывести её.
• 2 u v w: изменить веса всех вершин на пути из $u$ в $v$ на $w$.

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

Первая строка содержит $N$ ($2 \le N \le 100\,000$).

Вторая строка содержит веса вершин в порядке от $1$ до $N$.

Следующие $N-1$ строк содержат по два целых числа $u$ и $v$ — номера вершин, соединяемых $i$-м ребром.

Следующая строка содержит количество запросов $M$ ($1 \le M \le 100\,000$).

Далее $M$ строк содержат по одному запросу в каждой строке.

Абсолютное значение веса вершины не превышает $10\,000$.

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

Для каждого запроса выведите результат в отдельной строке в порядке их выполнения.

Примеры

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

5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5

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

5
9