L. Black and White Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes rooted at node $$$1$$$, and every node is colored either black or white.

Given $$$q$$$ queries consisting of a node $$$u$$$, your task is to count how many nodes $$$v$$$ exist in the subtree of node $$$u$$$ such that in the path from $$$u$$$ to $$$v$$$, the number of black nodes equals the number of white nodes, including $$$u$$$ and $$$v$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n \leq 10^{5}, 1 \leq q \leq 10^{5})-$$$ the number of nodes in the tree and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$c_{1},c_{2},...,c_{n}$$$ $$$(0\leq c_{i} \leq 1)$$$, where $$$c_{i}=0$$$ means that the $$$i_{th}$$$ node is white and $$$c_{i}=1$$$ means that the $$$i_{th}$$$ node is black.

Each of the next $$$n-1$$$ lines describes an edge of the tree. The $$$i_{th}$$$ edge is denoted by two integers $$$u_{i}$$$ and $$$v_{i}$$$, the labels of nodes it connects $$$(1\leq u{i},v_{i} \leq n, u_{i} \ne v_{i})$$$.

It is guaranteed that the given edges form a tree.

The next $$$q$$$ lines contain the queries. The $$$j_{th}$$$ line contains one integer $$$u$$$ $$$(1\leq u \leq n)$$$.

Output

Print $$$q$$$ integers $$$-$$$ the answers to the queries in the order they appear in the input.

Example
Input
3 3
1 0 1
1 2
3 2
1
2
3
Output
1
1
0