Cho một cây gồm ~n~ đỉnh và ~Q~ truy vấn. Trên mỗi đỉnh ~u~ của cây được gán một giá trị là ~C_u~. Mỗi truy vấn sẽ thuộc ~1~ trong ~2~ dạng như sau:

• ~1~ ~u~ ~v~ ~(1 \le u,v \le n)~ : tìm số các số khác nhau trong đường đi từ ~u~ đến ~v~.
• ~2~ ~x~ ~val~ ~(1 \le x \le n;~ ~0 \le val \le 10^9)~: gán giá trị ~val~ vào ~C_x~.

Input

• Dòng đầu tiên bao gồm hai số ~n~ và ~Q~ lần lượt là số đỉnh của cây và số truy vấn của bài (~1 \le n, Q \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên là các giá trị ~C_1, C_2, \dots, C_n~ (~0 \le C_i \le 10^9~).
• ~n - 1~ dòng tiếp theo chứa các cạnh của cây và trong đó mỗi dòng sẽ chứa ~2~ số ~u~ và ~v~ là hai đỉnh được nối với nhau bởi ~1~ cạnh (~1 \le u, v \le n~).
• ~Q~ dòng tiếp theo lần lượt là các truy vấn của bài toán.

Output

Ở mỗi truy vấn loại ~1~ sẽ in ra đáp án của truy vấn trên một dòng duy nhất.

Scoring

Sample Input 1

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

Sample Output 1

5
3
4
3
3