Given an Integer K and a tree of N vertices where each vertex consists of a value $V_i$ associated to it. Find the longest path in the tree which satisfies the following conditions

1. The number of vertices in the path should be a multiple of K.
2. Let's say there are $L \times K$ vertices in the path and $X_i$ be the value associated with $i^{th}$ vertex in that path, then $gcd( X_{i \times K+1}$, $X_{i \times K+2}$, $X_{i \times K+3}$, ... $X_{i \times K+K}) > 1$ $\forall i \in [0, L-1].$ where $gcd(x1, x2 ... xn)$ is the Greatest Common Divisor of the numbers $x1,x2... xn$.

Input Format
First line consists of two integers N and K.
Next $N-1$ lines consists of two integers $u_i$ and $v_i$ representing an edge between $u_i$ and $v_i$.
Next line consists of N space separated integers where $i^{th}$ of them is the value $V_i$ associated to $i^{th}$ vertex.

Output Format
Print an Integer representing the longest path as described in the problem statement.

Constraints

• $1 \le N \le 10^5$
• $1 \le K \le min(N,10)$
• $1 \le V_i \le 10^6$