This year, Patrick has decided use his immense power to launch a massive cyberattack on the Canadian Computing Competition's online grader. To set up the attack, he has prepared an ingenious exploit targetted at their servers and is now examining the possible attack vectors.

The CCC Grader's server cluster is organized as a tree with ~N~ servers (numbered ~1~ to ~N~) and ~N - 1~ connections. Server ~1~, which manages the grader itself, is designated as the root of the tree. Additionally, Patrick has assigned the servers distinct values ~a_1, a_2, ..., a_N~ which will be used in the attack.

Patrick's exploit is able to target any non-empty subtree in the server cluster and gain control over the entire cluster. However, some subtrees may be easier to exploit than others. The easiness score of a subtree is defined according to the following rules:

1. A set ~S~ is said to be good if it is closed under the bitwise exclusive or operation. In other words, it is good if, for all ~X, Y \in S~, ~X \oplus Y~ is also in ~S~. Note that it's possible that ~X = Y~.
2. For a given subtree, we define a set ~T~ which contains all of the values present in the subtree.
3. If ~T~ is good, the easiness of the subtree is ~0~. Otherwise, the easiness of the subtree is defined as the minimum number of elements that must be added to ~T~ to make it good.

Since Patrick has been procrastinating as usual, he is simply going to choose a random non-empty subtree to use the exploit on. He would like you to help him find out the average easiness score of all possible subtree choices, rounded down to the nearest integer.

Constraints

In all subtasks,

~2 \le N \le 10^5~

~1 \le u_i, v_i \le N~

~0 \le a_i < 2^{22}~

Subtask 1 [20%]

~2 \le N \le 22~

For all ~i~, ~a_i~ is ~2^{x_i}~ for some ~x_i \ge 0~.

Subtask 2 [80%]

No further constraints.

Input Specification

The first line will contain two space-separated integers, ~N~.

The next line will contain ~N~ space-separated integers, ~a_1, a_2, ..., a_N~.

The next ~N - 1~ will each contain two space-separated integers, ~u_i~ and ~v_i~, meaning that there's a connection between servers ~u_i~ and ~v_i~.

Output Specification

Output the average easiness of all subtrees, rounded down to the nearest integer.

Sample Input

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

Sample Output

2

Sample Explanation

The value ~0~ is added to the sets of the subtrees rooted at ~3~, ~4~, and ~5~ to form good sets of ~\{0, 3\}~, ~\{0, 4\}~, ~\{0, 5\}~. Therefore, the easiness scores of these subtrees are all ~1~.

Values of ~0~, ~1~, ~2~, ~6~, and ~7~ are added to the set of the subtree rooted at ~2~ to form a good set of ~\{0, 1, 2, 3, 4, 5, 6, 7\}~, for an easiness score of ~5~.

Values of ~0~, ~6~, and ~7~ are added to the subtree rooted at ~1~ to form the same good set as the one rooted at ~2~, for an easiness score of ~3~.

The average value is then ~\left \lfloor \frac{1 + 1 + 1 + 5 + 3}{5} \right \rfloor = 2~.

Note that the set ~\{0, 1, 2, 3, 4, 5, 6, 7\}~ is good because for any two elements, their exclusive or is also in the set. For example, ~3 \oplus 5 = 6~ which is in the set. ~4 \oplus 4 = 0~ is also in the set.