A. A Colorful Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Luiz, Carol, and Henrique agreed to meet at the park after the UnBalloon running club meeting to organize their team for the VII UnBalloon Marathon, the most anticipated race of the year. However, Luiz, being an excellent runner, finished the course before the rest of the team, coming in $$$3^{rd}$$$ place in the club (behind Maxwell and Arthur).

While waiting for Carol, who is slower due to a knee injury, and Henrique, who is still waiting for the bus, Luiz began observing the trees in the park. He noticed that one tree was quite different from the others, having several parts of distinct colors. Knowing that if he mentioned this, his team would rather investigate the colors instead of focusing on the upcoming marathon, help Luiz answer his teammates' various questions.

The tree observed by Luiz can be modeled as a connected acyclic undirected graph with $$$N$$$ nodes and $$$N-1$$$ edges, where the root is fixed at vertex $$$1$$$. Each node $$$i$$$ has an associated color, represented by an integer value $$$a_i$$$.

Your task is to help the team answer $$$Q$$$ queries. Each query consists of a node $$$x_i$$$, and you must determine the number of distinct colors present on the unique path between node $$$x_i$$$ and the root of the tree.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 10^5)$$$, representing the number of nodes in the tree and the number of queries, respectively.

The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ $$$(1 \leq a_i \leq 10^9)$$$, where $$$a_i$$$ denotes the color of the $$$i$$$-th node.

The following $$$N-1$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq N, u_i \neq v_i)$$$, representing an edge between nodes $$$u_i$$$ and $$$v_i$$$.

Finally, the next $$$Q$$$ lines each contain a single integer $$$x_i$$$ $$$(1 \leq x_i \leq N)$$$, representing a query for the number of distinct colors on the path from node $$$x_i$$$ to the root.

Output

For each query, print a single line containing a single integer representing the number of distinct colors found on the unique path between node $$$x_i$$$ and the root of the tree.

Examples
Input
4 2
1 2 3 4
1 2
2 3
3 4
3
4
Output
3
4
Input
4 2
1 2 3 2
1 2
2 3
3 4
3
4
Output
3
3