You are given a tree of ~N~ nodes, and an integer ~K~. Each node has a value ~v_i~. Determine the maximum XOR-sum of the values of a path with length ~\geq K~.

Note the length of a path is defined as how many edges are on that path, not how many nodes are on it.

We define the XOR-sum of a set of integers ~a~ to be ~a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_k~, where ~k~ is the length of ~a~.

Input Specification

The first line contains two integers ~N~ and ~K~ ~(1 \leq K < N \leq 10^5)~

The next line contains ~N~ integers ~v_i\ (0 \leq v_i \leq 10^9)~.

The next ~N-1~ lines contain two integers ~a_i~ and ~b_i~ ~(1 \leq a_i,b_i \leq N,\ a_i \neq b_i)~, the edges of the tree.

Output Specification

On one line, you are to output the maximum XOR-sum of a path with length ~\geq K~, or ~-1~ if no path exists.

Subtasks

Subtask 1 (10%)

~N \leq 10^3~

Subtask 2 (10%)

~v_i \in \{0,1\}~

Subtask 3 (10%)

All vertices will have degree at most 2

Subtask 4 (70%)

No further constraints.

Note the subtasks are disjoint, and you do not have to solve previous subtasks to solve a subtask.

Sample Input

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

Sample Output

5