Giá Trị Lớn Nhất Trên Đường

Cho một cây $n$ đỉnh đánh số $1,\dots ,n$. Đỉnh $i$ có giá trị nguyên $a_i$. Xử lý $q$ thao tác theo thứ tự:

• $1$ $s$ $x$: gán giá trị tại đỉnh $s$ bằng $x$;
• $2$ $u$ $v$: tìm giá trị lớn nhất trên đường đơn từ $u$ đến $v$, kể cả hai đầu.

Input

• Dòng đầu chứa $n$ $q$; dòng hai chứa $n$ giá trị. Tiếp theo là $n-1$ cạnh, rồi $q$ dòng thao tác.

Output

• In kết quả của mỗi thao tác loại $2$ trên một dòng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i,x\le 10^9$; $1\le s,u,v\le n$.
• Các cạnh tạo thành một cây vô hướng.

Scoring

• Subtask $1$ ($50\%$): $n,q\le 40$. Subtask $2$ ($50\%$): không có giới hạn bổ sung.

Example

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

7
4
9
4