Malnar 先生正在观察他的榕树，并得出结论认为它不够“灵活”。我们可以将他的榕树想象成一棵有 $n$ 个节点的树，其中每个节点都有其自身的灵活性 $F_i$。Malnar 先生将切除一组节点，使得剩余的树保持连通，且至少包含 $k$ 个节点。此时，树的灵活性定义为树内所有节点灵活性 $F_i$ 的按位与（bitwise AND）。现在他想知道他能达到的最大灵活性是多少。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $k$ ($1 \le k \le n$)，分别表示树的节点数和题目要求的节点数 $k$。

第二行包含 $n$ 个整数，其中第 $i$ 个数表示 $F_i$ ($0 \le F_i < 2^{30}$)。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示节点 $u_i$ 和 $v_i$ 之间有一条边相连。

输出格式

在唯一的一行中输出 Malnar 先生可以达到的最大灵活性。

样例

输入 1

5 4
6 2 7 10 5
1 2
2 3
2 4
1 5

输出 1

2

说明

第一个样例的解释：通过移除节点 5 可以达到最大灵活性。

输入 2

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

输出 2

2