Cho một cây gồm \(n\) đỉnh (cây là đồ thị vô hướng, liên thông và không có chu trình). Các đỉnh này được đánh số từ \(1\) đến \(n\). Mỗi đỉnh đều có chứa một giá trị.

Bạn cần thực hiện q truy vấn, có hai loại truy vấn khác nhau:

1. Thay đổi giá trị trên đỉnh \(s\) thành \(x\);
2. Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\): số lượng đỉnh và số lượng truy vấn;
• Dòng tiếp theo chứa \(n\) số nguyên dương \(v_1, v_2,\ldots v_n\): giá trị của mỗi đỉnh;
• Sau đó là \(n-1\) dòng mô tả các cạnh của cây. Mỗi dòng gồm hai số nguyên dương \(a\) và \(b\): thể hiện có cạnh nối giữa hai đỉnh \(a\), \(b\);
• Cuối cùng là \(q\) dòng thể hiện các truy vấn. Mỗi truy vấn thuộc một trong hai dạng: 1 s x hoặc 2 a b.

Output

• In ra câu trả lời cho các truy vấn loại 2, các giá trị được cách nhau bởi dấu cách.

Ràng buộc

• \(1\leq n, q\leq 2\times 10^5\);
• \(1\leq a, b, s\leq n\);
• \(1\leq v_i, x\leq10^9\).

Ví dụ

Sample input

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

Sample output

4 3