Marisa sống trong khu rừng ma thuật. Một trong những việc cô thường làm là hái nấm.

Khu rừng có thể được biểu diễn bằng một cây có ~n~ nút, ở nút thứ ~i~ là loại nấm có màu ~c_i~. Do đây là khu rừng ma thuật nên các cây nấm có khả năng đổi màu.

Cho ~q~ ngày, mỗi ngày một trong hai sự kiện sau sẽ diễn ra:

• Cây nấm ở nút ~i~ đổi màu thành ~c~.
• Marisa đi hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Với mỗi ngày Marisa đi hái nấm, hãy cho cô biết sẽ hái được bao nhiêu nấm nhé!

Input:

• Dòng đầu tiên là 2 số nguyên dương ~n, q~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~c_i \le n~ là màu của cây nấm ở đỉnh ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số nguyên dương ~u, v \le n~ thể hiện có đường đi trực tiếp giữa nút ~u~ và ~v~.
• ~q~ dòng tiếp theo là một trong 2 loại:
  • 1 i c, đổi màu cây nấm ở nút ~i~ thành ~c~.
  • 2 u v c, Marisa hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Output:

• Với mỗi ngày Marisa đi hái nấm, hãy in ra số lượng cây nấm cô hái được, cây nấm cô hái ngày hôm sau sẽ tự mọc lại và cùng màu với cây nấm cũ.

Sample Test:

Input:

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

Output:

2
2

Giới hạn:

• Subtask 1 (40% số điểm): ~n, q \le 1000~.
• Subtask 2 (30% số điểm): ~n, q \le 10^5~.
• Subtask 3 (30% số điểm): ~n, q \le 5 \times 10^5~.