Given a tree consisting of n nodes. Each node initially have a color c_i.
You are given mm commands, each of them is one of the follows:
The first line of the input contains two integers n(1≤n≤10^5) and m (1≤m≤5×10^5).
The second line contains n integers c1,c2,…,cn (1≤ci≤n).
Each of the following n - 1 lines contains two integers u, v (1≤u,v≤n,u!=v) - an edge of the tree.
Each of the following m lines contains one of the three commands listed above.
It's guaranteed that no edges is cut twice or more.
It's also guaranteed that in command of type 2 and 3, 1≤l≤r≤n, 1≤x,v≤n.
10 19
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 4
4 5
4 6
5 7
5 8
1 9
9 10
3 4 1 10
3 8 3 4
2 9 9 10 1
3 4 1 10
3 2 8 10
1 4
3 8 1 10
3 7 7 8
2 5 5 7 9
3 7 9 10
2 1 1 2 3
3 1 3 3
1 1
3 1 3 3
2 10 3 9 4
3 1 4 4
2 3 3 5 9
3 3 6 10
3 3 6 610
2
10
1
3
2
2
5
3
3
4
1