Thái được giao nhiệm vụ trang trí một cây thông noel có \(n\) đỉnh được đánh số từ \(1\) đến \(n\) và có gốc là đỉnh \(1\). Ban đầu, đỉnh thứ \(i\) sẽ có màu là \(c_i\). Thái được yêu cầu thực nhiệm \(4\) thao tác sau với cây:

• "1 u v x": Đổi màu tất cả đỉnh trên đường đi đơn từ \(u\) đến \(v\) thành màu \(x\).
• "2 u x": Đổi màu tất cả các đỉnh trong cây con gốc \(u\) thành màu \(x\).
• "3 u v": Đếm số màu phân biệt trên đường đi đơn từ \(u\) đến \(v\).
• "4 u": Đếm số màu phân biệt trong cây con gốc \(u\).

Dữ liệu vào

• Dòng đầu chứa số nguyên số \(n\) và \(q\) lần lượt là số đỉnh và số yêu cầu (\(1 \le n,q \le 2 \times 10^5\))
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) mô tả một cạnh của cây \((1 \le u,v \le n)\)
• Dòng tiếp theo chứa \(n\) số nguyên \(c_1,c_2...c_n\) \((1 \le c_i \le 60)\) mô tả màu ban đầu của các đỉnh.
• \(q\) dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên \(k\) \((1 \le k \le 4)\) theo sau là các số nguyên mô tả các yêu cầu \((1 \le u,v \le n, 1 \le x \le 60)\)

Dữ liệu ra

• Trả lời các truy vấn loại \(3\) và \(4\)

Input 1

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

Output 1

3
3
1
2