M. Friend Management
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Valentine's day is coming soon!! It is a special day not only for humans, but also for the dinosaurs living in Dinoland!

Danny, being a popular dinosaur, got asked out by many other Dinosaurs. Indeed, he received $$$K$$$ date invitations numbered from $$$1$$$ to $$$K$$$. The $$$i^{\text{th}}$$$ date invitation was sent to him by Dinosaur $$$i$$$.

However, there is a little problem. Danny has a group of $$$N$$$ friends, that can be modelled as a tree where each node represents one of Danny's friends. Two dinosaurs are called direct friends if there is an edge between them. Two dinosaurs are friends if there is a path between them, and we say that they belong to the same friend group. Each of Danny's friends is numbered from $$$1$$$ to $$$N$$$, and the $$$i^{\text{th}}$$$ of them has a value $$$a_i$$$ that represents their dating history.

If Danny accepts the $$$i^{\text{th}}$$$ date invitation for Saint Valentine, all of his friends who have dated the dinosaur who sent that invitation will get mad and leave the friend group. A friend $$$j$$$ will get mad when Danny accepts the $$$i^{\text{th}}$$$ date invitation if and only if $$$i$$$ divides $$$a_j$$$. When a dinosaur leaves the friend group, he will not be part of the group anymore and his ties with his direct friends will disappear. As a result, the group will be fragmented, and turn into multiple smaller friend groups.

Danny is weighing the pros and cons of accepting the invitations he got. He asked for your help. He wants you to tell him, for each invitation $$$i$$$ that he got, how many friend groups he will end up with.

Input

On the first line of input you are given two integers $$$N$$$ and $$$K$$$ $$$(1 \leq N, K \leq 10^6)$$$

On the second line of input, you are given $$$N$$$ integers $$$a_1a_2 ...a_N$$$ $$$( 1 \leq a_i \leq 10^6)$$$

On each of the next $$$N-1$$$ lines of input, you will be given two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v\leq N$$$) denoting that friends $$$u$$$ and $$$v$$$ are direct friends and that there is an edge between them. It is guaranteed that the friends form a tree.

Output

Print $$$K$$$ integers, the number of remaining friend groups if Danny excepts each invitation.

Example
Input
5 3
1 3 4 6 7
1 2
1 3
3 4
4 5
Output
0 2 1
Note

The friends' tree looks initially like this:

  • Accepting invitation $$$1$$$ will lead to Danny losing all his friends, and as a result, the number of friend groups remaining will be $$$0$$$
  • Accepting invitation $$$2$$$ will lead to Danny losing friends $$$3$$$ and $$$4$$$ which leads to two separate remaining friend groups.
  • Accepting invitation $$$3$$$ will lead to Danny losing friends $$$2$$$ and $$$4$$$ which leads to one remaining friend group.