Mr. Malnar has been observing his ficus and concluded that it is not flexible enough. We can imagine his ficus as a tree with $n$ nodes, where each node has its own flexibility $F_i$. Mr. Malnar will cut off a set of nodes such that the tree remains connected and at least $k$ nodes remain. The flexibility of the tree is then defined as the bitwise AND of $F_i$ for all nodes within the tree. He is now interested in the maximum flexibility he can achieve.

Input

The first line contains the integers $n$ ($1 \le n \le 10^5$) and $k$ ($1 \le k \le n$), representing the number of nodes in the tree and the number $k$ from the problem statement.

The second line contains $n$ integers, where the $i$-th integer denotes $F_i$ ($0 \le F_i < 2^{30}$).

The next $n - 1$ lines contain the integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), indicating that nodes $u_i$ and $v_i$ are connected by an edge.

Output

In the only line, print the maximum flexibility that Mr. Malnar can achieve.

Examples

Input 1

5 4
6 2 7 10 5
1 2
2 3
2 4
1 5

Output 1

2

Note 1

The maximum flexibility is achieved by removing node 5.

Input 2

4 2
3 1 3 2
1 2
2 3
3 4

Output 2

2