Первая строка содержит два целых числа $n$ и $k$ ($2 \leq n \leq 100\,000$, $1 \leq k \leq 20$)~--- количество вершин дерева и число $k$ соответственно.

Вторая строка содержит $n$ целых чисел $a_i$ ($0 \leq a_i < 2^k$)~--- значения вершин.

Следующие $n - 1$ строк описывают ребра дерева.

$i$-я из них содержит два целых числа $v_i$ и $u_i$ ($1 \leq v_i, u_i \leq n$)~--- номера вершин, соединенных $i$-м ребром.