Cho cây \(n\) đỉnh, đỉnh \(i\) có giá trị \(A_i\). Cho \(q\) truy vấn thuộc một trong hai dạng:

• "1 u x": đổi giá trị của đỉnh \(u\) thành \(x\).
• "2 u v": tìm giá trị lớn nhất trên đường đi đơn từ \(u\) tới \(v\).

Trả lời các truy vấn loại \(2\)!

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v\), có cạnh nối giữa đỉnh \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u,v\), một truy vấn.

Dữ liệu ra

• In ra đáp án cho mỗi truy vấn loại \(2\).

Ràng buộc

• \(1 \le n \le 2 \times 10^5\)
• \(1 \le A_i,x \le 10^9\)
• \(1 \le u,v \le n\)

Input 1

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

Output 1

5 9 9