Problem: The New Year holidays are over, but Resha doesn't want to throw away the New Year tree. He invited his best friends Kerim and Gural to help him to redecorate the New Year tree.

The New Year tree is an undirected tree with n vertices and root in the vertex 1.

You should process the queries of the two types:

  1. Change the colours of all vertices in the subtree of the vertex v to the colour c. 
  2. Find the number of different colours in the subtree of the vertex v. 

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 4·105) — the number of vertices in the tree and the number of the queries.

The second line contains n integers ci (1 ≤ ci ≤ 60) — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the vertices of the j-th edge. It is guaranteed that you are given correct undirected tree.

The last m lines contains the description of the queries. Each description starts with the integer tk (1 ≤ tk ≤ 2) — the type of the k-th query. For the queries of the first type then follows two integers vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — the number of the vertex whose subtree will be recoloured with the colour ck. For the queries of the second type then follows integer vk (1 ≤ vk ≤ n) — the number of the vertex for which subtree you should find the number of different colours.

Output

For each query of the second type print the integer a — the number of different colours in the subtree of the vertex given in the query.

Each of the numbers should be printed on a separate line in order of query appearing in the input.

Examples

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


Input

23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4


Output

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

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Aldo Culquicondor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int[] color;
        int[] start;
        int[] end;
        int time;
        Graph g;
        TreeColor st;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt(), m = in.nextInt();
            color = new int[n];
            IOUtils.read(in, color);
            start = new int[n];
            end = new int[n];
            g = new Graph(n, 2 * (n - 1));
            for (int i = 1; i < n; ++i)
                g.addBiEdge(in.nextInt() - 1, in.nextInt() - 1);
            time = -1;
            dfs(0, -1);
            st = new TreeColor(n);
            for (int i = 0; i < n; ++i)
                st.update(start[i], start[i], color[i]);

            for (int i = 0; i < m; ++i) {
                int t = in.nextInt(), v = in.nextInt() - 1;
                if (t == 1)
                    st.update(start[v], end[v], in.nextInt());
                else {
                    long r = st.query(start[v], end[v]);
                    out.println(Long.bitCount(r));
                }
            }
        }

        void dfs(int u, int p) {
            start[u] = ++time;
            for (int v : g.getAdjVertices(u))
                if (v != p)
                    dfs(v, u);
            end[u] = time;
        }

    }

    static class IOUtils {
        public static void read(InputReader in, int A[], int start, int end) {
            for (int i = start; i < end; ++i)
                A[i] = in.nextInt();
        }

        public static void read(InputReader in, int A[]) {
            read(in, A, 0, A.length);
        }

    }

    static class TreeColor extends LazyPropagation {
        public TreeColor(int n) {
            super(n, 0);
        }


        protected long merge(long x, long y) {
            return x | y;
        }


        protected long mergeAdd(long prev, long up) {
            return up;
        }


        protected long nodeUpdate(long prev, long up, int size) {
            return 1L << up;
        }

    }

    static abstract class SegmentTree {
        protected int n;
        protected long[] data;
        protected long defaultValue;

        protected static int upperPowTwo(int x) {
            return 1 << (32 - Integer.numberOfLeadingZeros(x - 1));
        }

        protected static int center(int x, int y) {
            return (x + y) >> 1;
        }

        protected static int left(int x) {
            return (x << 1) + 1;
        }

        public SegmentTree(int n, long defaultValue) {
            this.n = n;
            this.defaultValue = defaultValue;
            data = new long[upperPowTwo(n) << 1];
            Arrays.fill(data, defaultValue);
        }

        public SegmentTree(int n) {
            this(n, 0);
        }

        protected abstract long merge(long x, long y);

        public long query(int i, int j) {
            return query(i, j, 0, 0, n - 1);
        }

        long query(int i, int j, int idx, int l, int r) {
            int L = left(idx), R = L + 1;
            if (r < i || l > j)
                return defaultValue;
            if (l >= i && r <= j)
                return data[idx];
            int mid = center(l, r);
            return merge(query(i, j, L, l, mid), query(i, j, R, mid + 1, r));
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536);
            tokenizer = null;
        }

        public String next() {
            String line;
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    line = reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null)
                    throw new UnknownError();
                tokenizer = new StringTokenizer(line);
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class Graph {
        int[] prev;
        int[] last;
        protected int[] adj;
        protected int[] cnt;
        protected int edgeCount;
        protected int vertexCount;

        public Graph(int n, int m) {
            vertexCount = n;
            edgeCount = 0;
            adj = new int[m];
            prev = new int[m];
            last = new int[n];
            cnt = new int[n];
            Arrays.fill(last, -1);
        }

        public void addEdge(int from, int to) {
            adj[edgeCount] = to;
            prev[edgeCount] = last[from];
            last[from] = edgeCount++;
            ++cnt[from];
        }

        public void addBiEdge(int u, int v) {
            addEdge(u, v);
            addEdge(v, u);
        }

        public Iterable<Integer> getAdjVertices(int u) {
            return () -> new VertexIterator(this, u);
        }

        class EdgeIterator implements Iterator<Integer> {
            protected Graph graph;
            protected int edge;

            public EdgeIterator(Graph graph, int vertex) {
                this.edge = graph.last[vertex];
                this.graph = graph;
            }


            public boolean hasNext() {
                return edge != -1;
            }


            public Integer next() {
                int rEdge = edge;
                edge = graph.prev[edge];
                return rEdge;
            }

        }

        class VertexIterator extends EdgeIterator {
            public VertexIterator(Graph graph, int edge) {
                super(graph, edge);
            }


            public Integer next() {
                return graph.adj[super.next()];
            }

        }

    }

    static abstract class LazyPropagation extends SegmentTree {
        protected long[] add;

        public LazyPropagation(int n, long defaultValue) {
            super(n, defaultValue);
            add = new long[SegmentTree.upperPowTwo(n) << 1];
        }

        public LazyPropagation(int n) {
            this(n, 0);
        }

        protected abstract long nodeUpdate(long prev, long up, int size);

        void push(int idx, int l, int r, int L, int R) {
            if (add[idx] > 0) {
                data[idx] = nodeUpdate(data[idx], add[idx], r - l + 1);
                if (l != r) {
                    add[L] = mergeAdd(add[L], add[idx]);
                    add[R] = mergeAdd(add[R], add[idx]);
                }
                add[idx] = 0;
            }
        }

        public void update(int i, int j, long up) {
            update(i, j, up, 0, 0, n - 1);
        }

        void update(int i, int j, long up, int idx, int l, int r) {
            int L = SegmentTree.left(idx), R = L + 1;
            if (l >= i && r <= j)
                add[idx] = mergeAdd(add[idx], up);
            push(idx, l, r, L, R);
            if ((l >= i && r <= j) || r < i || l > j)
                return;
            int mid = SegmentTree.center(l, r);
            update(i, j, up, L, l, mid);
            update(i, j, up, R, mid + 1, r);
            data[idx] = merge(data[L], data[R]);
        }

        long query(int i, int j, int idx, int l, int r) {
            int L = SegmentTree.left(idx), R = L + 1;
            push(idx, l, r, L, R);
            if (l >= i && r <= j)
                return data[idx];
            if (r < i || l > j)
                return defaultValue;
            int mid = SegmentTree.center(l, r);
            return merge(query(i, j, L, l, mid), query(i, j, R, mid + 1, r));
        }

        protected long mergeAdd(long prev, long up) {
            return merge(prev, up);
        }

    }
}