Задано дерево с\textbf{ n }(\textbf{1 }≤ \textbf{n }≤ \textbf{200000}) вершинами и список из \textbf{q }(\textbf{1 }≤ \textbf{q }≤ \textbf{100000}) запросов. Необходимо обработать все запросы и вывести ответ для каждого из них. Дерево является связным, каждой вершине дерева приписан вес \textbf{w_i} (\textbf{−10000 }≤ \textbf{w_i} ≤ \textbf{10000}). Каждый запрос состоит из числа \textbf{t_i} (\textbf{t_i = 1}, \textbf{2}) - типа запроса, и трех чисел \textbf{a_i}, \textbf{b_i} и \textbf{c_i} (\textbf{1 }≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{n}, \textbf{−10000 }≤ \textbf{c_i} ≤ \textbf{10000}). В зависимости от типа запроса необходимо совершить следующее: \begin{itemize} \item (\textbf{t_i = 1}: запрос модификации) Изменить веса всех вершин по кратчайшему пути между \textbf{a_i} и \textbf{b_i} (обе включительно) на \textbf{c_i}. \item (\textbf{t_i = 2}: запрос вывода) Сначала создайте список весов вершин по кратчайшему пути между \textbf{a_i} и \textbf{b_i} (обе включительно) в порядке обхода. Затем выведите максимальную сумму непустой подряд идущей подпоследовательности весов в списке. Значение \textbf{c_i} игнорируется в этом типе запроса. \end{itemize} \InputFile Первая строка содержит два целых числа \textbf{n} и \textbf{q}. Во второй строке заданы \textbf{n} целых чисел \textbf{w_1}, \textbf{w_2}, ..., \textbf{w_n}. Каждая из следующих \textbf{n−1} строк состоит из двух чисел \textbf{s_i} и \textbf{e_i} (\textbf{1 }≤ \textbf{s_i}, \textbf{e_i} ≤ \textbf{n}), означающих присутствие ребра между \textbf{s_i} и \textbf{e_i}. Следующие \textbf{q} строк задают список запросов, каждая из которых состоит из четырех целых чисел в приведенном ниже формате. Запросы следует обрабатывать последовательно сверху вниз. \OutputFile Для каждого запроса вывести в отдельной строке наибольшую сумму.