City Attractions

Moldova has $N$ cities, numbered 1 through $N$, and bidirectional roads join some pairs of them. To keep the budget small the government built exactly $N - 1$ roads, and you can still travel between any two cities along them.

By national decree every city has a non-negative integer beauty. City $i$ has beauty $a_i$. Two different cities may have equal beauty.

Gigel has arrived in Moldova and is in city 1. He wants to see many beautiful cities, but his time is short and he cannot make up his mind. He stays for $K$ more days and visits one city each day. On day $i$ he starts from the city $x$ he ended the previous day in ($x = 1$ on the first day) and looks for a city $y$ with $y \ne x$ that maximizes $a_y - d(x, y)$, where $d(x, y)$ is the smallest number of roads on a route from $x$ to $y$. If several cities reach that maximum, he takes the one with the smallest index. He travels to $y$ and spends the rest of day $i$ there. The next day he applies the same rule again.

Write a program that finds the city Gigel is in at the end of day $K$.

The first line contains two integers $N$ and $K$, the number of cities and the number of days Gigel stays. The second line contains $N$ integers $a_1, a_2, \dots, a_N$, where $a_i$ is the beauty of city $i$. Each of the next $N - 1$ lines contains two integers $u_i$ and $v_i$, meaning that a bidirectional road joins city $u_i$ and city $v_i$.

Print one integer, the index of the city Gigel is in at the end of day $K$.

• $2 \le N \le 3 \times 10^5$
• $1 \le K \le 10^{18}$
• $0 \le a_i \le 10^9$
• $1 \le u_i, v_i \le N$
• $u_i \ne v_i$
• The $N - 1$ roads connect all cities.

In the first example Gigel leaves city 1 for city 3 on day 1, moves from city 3 to city 5 on day 2, and moves from city 5 to city 2 on day 3. On day 4, the last day, he leaves city 2 for city 5 again.