Vương quốc Anpha có ~N~ địa điểm tham quan được đánh số từ ~1~ đến ~N~, chúng kết nối với nhau bởi ~N - 1~ con đường hai chiều, giữa hai địa điểm tham quan khác nhau có không quá một con đường nối giữa chúng và không có con đường nào nối một địa điểm với chính nó. Mỗi địa điểm ~i~ có một giá trị di sản văn hóa là ~V_i~.

Một đoàn du khách muốn thực hiện các chuyến hành trình khám phá. Tuy nhiên, họ có một quy tắc tham quan rất khắt khe: Trong một chuyến đi từ địa điểm ~u~ đến địa điểm ~v~, họ chỉ dừng lại tham quan một địa điểm nếu giá trị di sản của nó không nhỏ hơn giá trị di sản của tất cả các địa điểm mà họ đã thực sự dừng lại tham quan trước đó trong cùng chuyến đi.

Yêu cầu:

Có ~Q~ sự kiện xảy ra thuộc một trong hai loại:

1. Cập nhật: ~1~ ~u~ ~new\_V~ - Giá trị di sản của địa điểm ~u~ thay đổi thành ~new\_V~.

2. Truy vấn: ~2~ ~u~ ~v~ - Cho biết số lượng địa điểm tối đa mà đoàn du khách sẽ dừng lại tham quan khi đi từ ~u~ đến ~v~.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 10^5)~.

• Dòng thứ hai gồm ~N~ số nguyên ~V_1, V_2, \dots, V_N~ ~(1 \le V_i \le 10^9)~.

• ~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x~, ~y~ ~(1 \le x, y \le N)~ mô tả một con đường nối giữa địa điểm ~x~ và ~y~.

• ~Q~ dòng cuối cùng, mỗi dòng mô tả một sự kiện theo định dạng đã nêu.

Output

Với mỗi truy vấn loại ~2~, in ra một số nguyên duy nhất là số lượng địa điểm tham quan được.

Scoring

Sample Input 1

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

Sample Output 1

3
2