## Maximum XOR Path

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

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 to be , where is the length of .

#### Input Specification

The first line contains two integers and

The next line contains integers .

The next lines contain two integers and , the edges of the tree.

#### Output Specification

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

#### Subtasks

##### Subtask 1 (10%)

##### Subtask 2 (10%)

##### 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`

## Comments