Tết sắp đến, bên cạnh việc kinh doanh, ông còn muốn ngôi nhà của ông phải thật đẹp vào ngày tết. Ông Z quyết định mua về cho nhà một chậu cây thật to và trang trí bằng những bóng đèn đầy màu sắc để cầu mong may mắn cho gia đình.

Chậu cây của ông Z gồm có \(n\) nút và nút \(1\) là gốc của cây, mỗi nút trên cây sẽ được trang trí bằng một bóng đèn. Vì quá bận với công việc kinh doanh nên ông ấy nhờ các bạn giúp đỡ. Bạn có dãy \(m\) thao tác cần làm chia làm 2 loại:

• Loại 1: Đổi màu tất cả nút của cây con gốc \(v\) thành màu \(c\).

• Loại 2: Tìm số lượng màu khác nhau trong cây con gốc \(v\).

Dữ liệu vào:

Dòng đầu tiên gồm 2 số \(n, m\) (\(1 \leq n \leq 10^5, 1 \leq m \leq 4 * 10^5\)) lần lượt là số nút trên cây và số lượng thao tác cần thực hiện

Dòng thứ hai gồm \(n\) số nguyên, số thứ \(i\) là màu ban đầu của bóng đèn trong trí cho nút thứ \(i\) \((1 \leq a[i] \leq 60)\)

\(n - 1\) dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) (\(1 \leq u, v \leq n\)) - có cạnh nối trực tiếp giữa 2 nút \(u\) và \(v\)

\(m\) dòng cuối cùng mỗi dòng biểu thị chi loại thao tác các bạn sẽ thực hiện:

• \(1\ v\ c\) : Đổi màu tất cả nút của cây con gốc \(v\) thành màu \(c\) \((1 \leq c \leq 60)\).

• \(2\ v\) : Tìm số lượng màu khác nhau trong cây con gốc \(v\).

Dữ liệu ra:

Gồm một số dòng trả lời cho thao tác loại 2.

Ví dụ

Input:

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

Output:

2
3
4
5
1
2