Truy vấn cây

Cho một cây có \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Mỗi đỉnh có một giá trị ban đầu.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• Thay đổi giá trị của đỉnh \(s\) thành \(x\).
• 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 \(n\) và \(q\) \((1 \leq n, q \leq 2 \cdot 10^5)\) -- số đỉnh của cây và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) \((1 \leq v_i \leq 10^9)\) -- giá trị của mỗi đỉnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).

• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có một trong hai dạng sau:

• 1 s x: Thay đổi giá trị của đỉnh \(s\) thành \(x\) \((1 \leq s \leq n, 1 \leq x \leq 10^9)\).

• 2 a b: Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\) \((1 \leq a, b \leq n)\).

Output

• In ra \(Q\) số nguyên trên một dòng duy nhất biểu thị giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Example

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

4 3