Bạn được giao cho việc là trang trí một cây gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\) và có gốc là đỉnh \(1\). Ban đầu, đỉnh thứ \(i\) có màu là \(c_{i}\). Bạn được yêu cầu thực hiện \(4\) thao tác sau với cây:

• \(1\) \(u\) \(v\) \(x\): Đổi màu tất cả cá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\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\) lần lượt số đỉnh và số yêu cầu.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) mô tả một cạnh của cây.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_{1}, c_{2}, \ldots, c_{n}\) \((1 \leq c_{i} \leq 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 \leq k \leq 4)\) và theo sau là các số nguyên mô tả các yêu cầu \((1 \leq u, v \leq n, 1 \leq x \leq 60)\):
  • Nếu \(k = 1\) thì theo sau là \(3\) số nguyên \(u, v\) và \(x\) mô tả thao tác loại \(1\).
  • Nếu \(k = 2\) thì theo sau là \(2\) số nguyên \(u\) và \(x\) mô tả thao tác loại \(2\).
  • Nếu \(k = 3\) thì theo sau là \(2\) số nguyên \(u\) và \(v\) mô tả thao tác loại \(3\).
  • Nếu \(k = 4\) thì theo sau là số nguyên \(u\) mô tả thao tác loại \(4\).

Output

• Với mỗi yêu cầu thao tác \(3\) hoặc thao tác \(4\), in ra kết quả trên từng dòng.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(1 \leq n, q \leq 1000\).
• Subtask \(2\) (\(18\%\) số điểm): \(1 \leq n, q \leq 5 \times 10^{4}\), \(1 \leq c_{i}, x \leq 30\), \(k = 2\) hoặc \(k = 4\).
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq n, q \leq 5 \times 10^{4}, 1 \leq c_{i}, x \leq 30\), mỗi đỉnh kề với không quá \(2\) đỉnh khác.
• Subtask \(4\) (\(22\%\) số điểm): \(1 \leq n, q \leq 5 \times 10^{4}, 1 \leq c_{i}, x \leq 20\).
• Subtask \(5\) (\(24\%\) số điểm): Không có điều kiên gì thêm.

Example

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

1
1
1

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

4
4
4