The first line contains two integers $n$ and $k$ ($2 \leq n \leq 100\,000$, $1 \leq k \leq 20$) --- the number of vertices in the tree and the number $k$, respectively.

The second line contains $n$ integers $a_i$ ($0 \leq a_i < 2^k$) --- the values of the vertices.

The next $n - 1$ lines describe the edges of the tree.

The $i$-th of them contains two integers $v_i$ and $u_i$ ($1 \leq v_i, u_i \leq n$) --- the indices of the vertices connected by the $i$-th edge.