Khu du lịch MZY nổi tiếng với những bản làng nép bên sườn núi, những ruộng bậc thang, các cung đèo uốn lượn và những điểm "săn mây" đầy hấp dẫn. Để thiết kế các hành trình khám phá, Ban quản lý khu du lịch mô hình hóa toàn bộ khu vực thành ~n~ điểm tham quan, được đánh số từ ~1~ đến ~n~. Giữa các điểm tham quan có đúng ~n-1~ tuyến đường hai chiều. Hệ thống đường đi liên thông và không có chu trình, vì vậy giữa hai điểm bất kỳ luôn tồn tại duy nhất một đường đi. Mỗi điểm tham quan ~i~ có một chỉ số trải nghiệm ~A_i~ ~(1 \le i \le n)~, là một số nguyên dương thể hiện mức độ hấp dẫn của điểm đó tại thời điểm hiện tại.

Một đoàn du khách thực hiện hành trình đi từ điểm ~u~ đến điểm ~v~. Để mỗi lần dừng chân đều thật sự đáng nhớ, đoàn du khách áp dụng quy tắc sau: họ phải dừng lại ở một điểm nếu chỉ số trải nghiệm của điểm đó không nhỏ hơn mọi chỉ số trải nghiệm đã gặp trước đó trên hành trình.

Yêu cầu: Có ~Q~ sự kiện, mỗi sự kiện thuộc một trong hai loại:

• Loại 1: ~1\ u\ x~ – thay chỉ số trải nghiệm ~A_u = x~.

• Loại 2: ~2\ u\ v~ – cho biết số điểm tham quan nhiều nhất mà đoàn du khách sẽ dừng lại khi đi từ ~u~ đến ~v~ theo quy tắc ở trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~Q~ (~n, Q \le 10^5~);

• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, \dots, A_n~ (~A_i \le 10^9~);

• ~n-1~ dòng tiếp theo: mỗi dòng chứa hai số nguyên ~x, y~ mô tả một tuyến đường nối trực tiếp hai điểm ~x~ và ~y~ (~1 \le x, y \le n~);

• ~Q~ dòng cuối cùng: mỗi dòng mô tả một sự kiện theo một trong hai dạng: ~1\ u\ x~ với ~1 \le u \le n, 1 \le x \le 10^9~; hoặc ~2\ u\ v~ với ~1 \le u, v \le n~.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Với mỗi sự kiện Loại 2, ghi ra một dòng chứa một số nguyên duy nhất là số điểm tham quan nhiều nhất mà đoàn du khách sẽ dừng lại khi đi từ ~u~ đến ~v~ theo quy tắc ở trên. Biết rằng, đoàn du khách có dừng lại tại đỉnh ~u~.

Scoring

Sample Input 1

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

Sample Output 1

2
3

Notes

Sự kiện 1 ~(2\ 5\ 7)~: đường đi ~5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6 \rightarrow 7~, có ~2~ điểm dừng thỏa mãn là điểm ~5~ và điểm ~2~.