One day, C and K felt bored and decided to play a classic game:

On a rooted tree with $n$ nodes, node $i$ contains $a_i$ tokens. Players take turns. In each turn, a player can move one token from any node $u$ to any node $v \in U(u)$, where $U(u) = \text{subtree}\{u\} \setminus \{u\}$ is the set of nodes in the subtree of $u$ (excluding $u$ itself). The player who cannot make a move loses.

As students at P** and T**, C and K found this game, where the winning strategy is obvious at a glance, quite dull. They decided it would be more interesting if each person had a special ability:

Before the game starts, C may choose to change the current root $R$ of the tree to any node $R^{\prime}$ adjacent to $R$. Two nodes are adjacent if and only if they are directly connected by an edge.

Before the game starts, K must choose one node on the tree and add one token to it.

C and K decide to play $m$ rounds. Each round proceeds as follows:

1. Before the game starts, C and K agree to place a token on node $x$ and set the root to $y$.
2. C then chooses whether to use their special ability. After C makes their decision, K chooses whether to use their special ability.
3. After the decisions regarding special abilities are made, the game is played on this tree with C going first and K going second. After the game, the state of the tokens on the tree is restored to the state at the end of step 1.

C thinks this game could be a simple problem, so he decides to test you: in the second step of each round, how many ways can C make a decision such that, regardless of how K uses their special ability, C has a winning strategy? Two decision methods are different if and only if the changed root $R^{\prime}$ is different, or if only one of them involves not using the special ability.

Input

The first line contains an integer representing the score of the subtask this test case belongs to. You can use this information to determine the special properties satisfied by this test case. Specifically, in the provided samples, this line uses $0$.

The second line contains two space-separated positive integers $n, m$, representing the number of nodes in the tree and the number of rounds, respectively. The nodes are numbered from $1$ to $n$.

The next $n-1$ lines each contain two space-separated positive integers $u_i, v_i$, representing an edge between nodes $u_i$ and $v_i$.

The next line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$.

The next $m$ lines each contain two space-separated positive integers $x, y$ describing a round of the game.

Output

Output $m$ lines. The $i$-th line should contain a non-negative integer $x$ representing the number of ways C can use their special ability such that C has a winning strategy in that round. Note that not using the special ability is also a potentially viable decision.

Examples

Input 1

0
5 2
1 2
1 3
2 4
2 5
1 0 1 0 1
2 2
4 4

Output 1

2
1

Note 1

In the first round, C has two ways to win: do not use the special ability, or change the root to node 1.

In the second round, C has only one way to win: change the root to node 2.

Examples 2-4

See the provided files.

Constraints

For all data, it is guaranteed that $1 \le n, m \le 1000000$, $0 \le a_1, a_2, \ldots, a_n \le 10^9$, $1 \le u_i, v_i \le n$, and $1 \le x, y \le n$.