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:
//package baobab;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class MOtrees {

    static List<Integer>[] graph;
    static int[] lkm;

    static int[] entries;
    static int[] exits;
    static int[] gen;
    static int genPointer;

    static int[] cc;
    static int[] colors;

    public static void main(String[] args) {
        IO scanner = new IO();
        int n = scanner.nextInt();
        int queryAmount = scanner.nextInt();
        colors = new int[n+1];
        for (int i=1; i<=n; i++) {
            colors[i] = scanner.nextInt();
        }
        graph = new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i=1; i<n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }
        entries = new int[n+1];
        exits = new int[n+1];
        gen = new int[n+1];
        genPointer = 1;
        dfs(1);

        lkm = new int[n+1];
        Query.n = n;
        Query.blocks = (int) (Math.sqrt(n));
        PriorityQueue<Query> queries = new PriorityQueue<>();
        for (int i=0; i<queryAmount; i++) {
            int root = scanner.nextInt();
            int size = scanner.nextInt();
            int a = entries[root];
            int b = exits[root];
            queries.add(new Query(a, b, size, i));
        }
        cc = new int[(int)1e5+1];
        int[] ans = new int[queryAmount];
        int left = 1;
        int right = 0;
        while (!queries.isEmpty()) {
            Query query = queries.poll();
            while (right < query.b) {
                int luku = gen[++right];
                addColorOf(luku);
            }
            while (left > query.a) {
                int luku = gen[--left];
                addColorOf(luku);
            }
            while (right > query.b) {
                int luku = gen[right--];
                removeColorOf(luku);
            }
            while (left < query.a) {
                int luku = gen[left++];
                removeColorOf(luku);
            }
            if (query.size < lkm.length) ans[query.idx] = lkm[query.size];
        }
        for (Integer a : ans) {
            System.out.println(a);
        }
    }

    static void addColorOf(int luku) {
        int color = colors[luku];
        cc[color]++;
        int newCount = cc[color];
        lkm[newCount]++;
    }

    static void removeColorOf(int luku) {
        int color = colors[luku];
        int oldCount = cc[color];
        lkm[oldCount]--;
        cc[color]--;
    }

    static void dfs(int node) {
        if (entries[node] > 0) return;
        gen[genPointer] = node; // entry
        entries[node] = genPointer++;
        for (int neighbor : graph[node]) {
            dfs(neighbor);
        }
        exits[node] = genPointer - 1;
    }

}

class FenwickSum {
    public int[] d;

    public FenwickSum(int n) {
        d=new int[n+1];
    }

    void modify(int i, long v) {
        i++;
        while (i<d.length) {
            d[i] += v;
            // Move to next uplink on the RIGHT side of i
            i += (i&-i);
        }
    }

    /** Returns sum from a to b, *BOTH* inclusive. */
    int getSum(int a, int b) {
        a++;
        b++;
        return getSum(b) - getSum(a-1);
    }

    private int getSum(int i) {
        int sum = 0;
        while (i>0) {
            sum += d[i];
            // Move to next uplink on the LEFT side of i
            i -= (i&-i);
        }
        return sum;
    }
}

class Query implements Comparable<Query> {
    int a;
    int b;
    int size;
    int block;
    int idx;
    static int blocks;
    static int n;

    public Query(int a, int b, int size, int idx) {
        this.a = a;
        this.b = b;
        this.size = size;
        this.idx = idx;
        this.block = (int) ((1.0 * a / n) * blocks);
    }

    @Override
    public int compareTo(Query o) {
        if (this.block != o.block) {
            return this.block - o.block;
        }
        return this.b - o.b;
    }

}

class IO extends PrintWriter {
    private InputStreamReader r;
    private static final int BUFSIZE = 1 << 15;
    private char[] buf;
    private int bufc;
    private int bufi;
    private StringBuilder sb;

    public IO() {
        super(new BufferedOutputStream(System.out));
        r = new InputStreamReader(System.in);

        buf = new char[BUFSIZE];
        bufc = 0;
        bufi = 0;
        sb = new StringBuilder();
    }

    private void fillBuf() throws IOException {
        bufi = 0;
        bufc = 0;
        while(bufc == 0) {
            bufc = r.read(buf, 0, BUFSIZE);
            if(bufc == -1) {
                bufc = 0;
                return;
            }
        }
    }

    private boolean pumpBuf() throws IOException {
        if(bufi == bufc) {
            fillBuf();
        }
        return bufc != 0;
    }

    private boolean isDelimiter(char c) {
        return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
    }

    private void eatDelimiters() throws IOException {
        while(true) {
            if(bufi == bufc) {
                fillBuf();
                if(bufc == 0) throw new RuntimeException("IO: Out of input.");
            }

            if(!isDelimiter(buf[bufi])) break;
            ++bufi;
        }
    }

    public String next() {
        try {
            sb.setLength(0);

            eatDelimiters();
            int start = bufi;

            while(true) {
                if(bufi == bufc) {
                    sb.append(buf, start, bufi - start);
                    fillBuf();
                    start = 0;
                    if(bufc == 0) break;
                }

                if(isDelimiter(buf[bufi])) break;
                ++bufi;
            }

            sb.append(buf, start, bufi - start);

            return sb.toString();
        } catch(IOException e) {
            throw new RuntimeException("IO.next: Caught IOException.");
        }
    }

    public int nextInt() {
        try {
            int ret = 0;

            eatDelimiters();

            boolean positive = true;
            if(buf[bufi] == '-') {
                ++bufi;
                if(!pumpBuf()) throw new RuntimeException("IO.nextInt: Invalid int.");
                positive = false;
            }

            boolean first = true;
            while(true) {
                if(!pumpBuf()) break;
                if(isDelimiter(buf[bufi])) {
                    if(first) throw new RuntimeException("IO.nextInt: Invalid int.");
                    break;
                }
                first = false;

                if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                    if(ret < -214748364) throw new RuntimeException("IO.nextInt: Invalid int.");
                    ret *= 10;
                    ret -= (int)(buf[bufi] - '0');
                    if(ret > 0) throw new RuntimeException("IO.nextInt: Invalid int.");
                } else {
                    throw new RuntimeException("IO.nextInt: Invalid int.");
                }

                ++bufi;
            }

            if(positive) {
                if(ret == -2147483648) throw new RuntimeException("IO.nextInt: Invalid int.");
                ret = -ret;
            }

            return ret;
        } catch(IOException e) {
            throw new RuntimeException("IO.nextInt: Caught IOException.");
        }
    }

    public long nextLong() {
        try {
            long ret = 0;

            eatDelimiters();

            boolean positive = true;
            if(buf[bufi] == '-') {
                ++bufi;
                if(!pumpBuf()) throw new RuntimeException("IO.nextLong: Invalid long.");
                positive = false;
            }

            boolean first = true;
            while(true) {
                if(!pumpBuf()) break;
                if(isDelimiter(buf[bufi])) {
                    if(first) throw new RuntimeException("IO.nextLong: Invalid long.");
                    break;
                }
                first = false;

                if(buf[bufi] >= '0' && buf[bufi] <= '9') {
                    if(ret < -922337203685477580L) throw new RuntimeException("IO.nextLong: Invalid long.");
                    ret *= 10;
                    ret -= (long)(buf[bufi] - '0');
                    if(ret > 0) throw new RuntimeException("IO.nextLong: Invalid long.");
                } else {
                    throw new RuntimeException("IO.nextLong: Invalid long.");
                }

                ++bufi;
            }

            if(positive) {
                if(ret == -9223372036854775808L) throw new RuntimeException("IO.nextLong: Invalid long.");
                ret = -ret;
            }

            return ret;
        } catch(IOException e) {
            throw new RuntimeException("IO.nextLong: Caught IOException.");
        }
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

}