Bài toán

Cho một cây có ~ n ~ đỉnh, mỗi đỉnh có một giá trị ban đầu. Nhiệm vụ của bạn là xử lý hai loại truy vấn:

1. Cập nhật giá trị của đỉnh ~ s ~: Đặt giá trị của đỉnh ~ s ~ thành ~ x ~.
2. Tìm giá trị lớn nhất trên đường từ ~ a ~ đến ~ b ~: Tìm giá trị lớn nhất của các đỉnh nằm trên đường từ ~ a ~ đến ~ b ~.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số lượng đỉnh và số lượng truy vấn (~ 1 \leq n, q \leq 2 \cdot 10^5 ~).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ v_1, v_2, \ldots, v_n ~: giá trị ban đầu của các đỉnh.
• Tiếp theo là ~ n-1 ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: biểu diễn một cạnh giữa hai đỉnh ~ a ~ và ~ b ~.
• Cuối cùng là ~ q ~ dòng, mỗi dòng là một truy vấn thuộc một trong hai dạng:
  • 1 s x: đặt giá trị của đỉnh ~ s ~ thành ~ x ~.
  • 2 a b: tìm giá trị lớn nhất trên đường từ ~ a ~ đến ~ b ~.

Đầu ra

• Với mỗi truy vấn dạng 2 a b, in ra giá trị lớn nhất trên đường từ ~ a ~ đến ~ b ~.

Ví dụ:

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

Output:

4 3