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\)