Problem: You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.

In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output

Print m integers — the answers to the queries in the order the queries appear in the input.

Examples

Input

8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3


Output

2
2
1
0
1


Input

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


Output

4

Note

A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

Solution (in JAVA):

Solution:
/**
 * Created by Aminul on 8/29/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF375D {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int n = in.nextInt(), q = in.nextInt();
        g = genList(n+1);
        c = new int[n+1]; color = new int[n+1];
        start = new int[n+1]; end = new int[n+1];

        for (int i = 1; i <= n; i++) {
            c[i] = in.nextInt();
        }
        for (int i = 1; i < n; i++) {
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v); g[v].add(u);
        }

        dfs(1, 0);

        Node[] queries = new Node[q];
        for (int i = 0; i < q; i++) {
            int u = in.nextInt(), k = in.nextInt();
            queries[i] = new Node(start[u], end[u], k, i);
        }

        int ans[] = MO((int)1e5, q, color, queries);

        for(int i : ans) pw.println(i);

        pw.close();
    }
    static int c[], color[], start[], end[], time = 0;
    static List<Integer> g[];
    static void dfs(int u, int p){
        start[u] = ++time;
        color[time] = c[u];
        for(int v : g[u]) if(v != p) dfs(v, u);
        end[u] = time;
    }

    static int[] MO(int n, int q, int a[], Node[] queries){
        BLOCK = (int) sqrt(n);
        Arrays.sort(queries);
        int [] ans = new int[q];
        int count[] = new int[n+1], freq[] = new int[n+1];

        int l = 1, r = 0, x;
        for(Node p : queries){
            while( r < p.v){
                r++; x = a[r];
                add(count, freq, x);
            }
            while( r > p.v){
                x = a[r];
                remove(count, freq, x);
                r--;
            }
            while( l > p.u){
                l--; x = a[l];
                add(count, freq, x);
            }
            while( l < p.u){
                x = a[l];
                remove(count, freq, x);
                l++;
            }
            ans[p.idx] = freq[p.k];
        }
        return ans;
    }

    static void add(int count[], int freq[], int x){
        freq[++count[x]]++;
    }

    static void remove(int count[], int freq[], int x){
        freq[count[x]--]--;
    }

    static int BLOCK = 320;
    static class Node implements Comparable<Node>{
        public int u, v, k, idx;
        public Node(int uu, int vv, int kk,  int i){
            u = uu; v = vv; k = kk; idx = i;
        }
        public int compareTo(Node n){
            if(u / BLOCK != n.u / BLOCK) return u - n.u;
            else return v - n.v;
        }
    }


    static <T>List<T>[] genList(int n){
        List<T> list[] = new List[n];
        for(int i = 0; i < n; i++) list[i] = new ArrayList<T>();
        return list;
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}