Tèo là một nhà thám hiểm đang khảo sát sức mạnh quân sự của các làng trong vương quốc. Có \(N\) làng, các làng được kết nối bởi \(N-1\) con đường tạo thành cấu trúc cây, mỗi làng \(i\) có chỉ số sức mạnh \(a_i\).

Tèo muốn tìm "điểm yếu nhất" (chỉ số sức mạnh nhỏ nhất) trong một nhánh và đôi khi cập nhật chỉ số sức mạnh của một làng.

Cụ thể, có \(Q\) truy vấn thuộc hai loại:

• 1 u val: Cập nhật chỉ số sức mạnh của làng \(u\) thành \(val\).
• 2 u: Tìm chỉ số sức mạnh nhỏ nhất trong nhánh gốc \(u\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn.

Kết quả ra

• Với mỗi truy vấn loại 2, in ra chỉ số sức mạnh nhỏ nhất trong nhánh.

Ví dụ

Input

5 5
5 3 8 2 7
1 2
2 3
2 4
1 5
2 2
1 4 1
2 2

Output

2
1

Ràng buộc

• Subtask 1 (20 điểm): \(N, Q \le 100\).
• Subtask 2 (20 điểm): \(N, Q \le 5000\).
• Subtask 3 (30 điểm): \(N, Q \le 10^5\), không có truy vấn cập nhật.
• Subtask 4 (30 điểm): Không có ràng buộc gì thêm.