Battle of FurfuriNagar

The country FurfuriNagar is famous for the cartoon series Motu Patlu. The peace and furfuriness of the country were unbearable for the world's most terrifying gang Jingalala. Therefore they have decided to take control over the country.

There are $n$ cities numbered from $1$ to $n$ in FurfuriNagar. Each pair of cities are connected with exactly one simple path. More formally the cities maintain a tree structure. The gang Jingalala consists of $x$ terrorists. They want to start attacking from any arbitrary city of FurfuriNagar and take control over as many cities as possible. The $i$-th city has $a_i$ armies to protect the city. When the gang attacks a city, if the number of armies of that city is greater than the number of terrorists who attacked the city, then all the terrorists are killed and they can’t win that city. Otherwise, they kill half of the armies and the remaining armies join their gang. (Formally, they kill $\lceil\frac{a_i}{2} \rceil$ armies of the $i$-th city). Thus they win a city. After winning each city, the gang members of that city get divided into groups and attack the adjacent unattacked cities. The gang is not allowed to visit a city twice.

They know the map of FurfuriNagar and the number of armies of each city. Now it’s time to find the optimal way to divide the gang members after winning each city so that they can win as many cities as possible. Now for each city, they want to know the maximum number of cities they can win, if they start attacking from that city. As you are a good programmer, they kidnapped you to solve the task.

Input

The first line of the input contains two integers $n$$(1 \leq n \leq 100)$ and $(1 \leq x \leq 10^{9}),$ denoting the number of cities and the number of terrorists.

The next line contains $n$ space-separated integers $a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^{9})$ denoting the number of armies of each city.

Each of the following $n-1$ lines contains two integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$ denoting a road between the city $u$ and $v$.

Output

Print $n$ space-separated integers. The $i$-th integer should be the maximum number of cities they can win if they start attacking from the $i$-th city.

Samples

Input	Output
7 3 3 2 4 4 5 1 2 1 2 2 3 2 4 1 5 5 6 5 7	3 5 0 0 0 1 1

Input	Output
5 3 4 1 2 5 3 1 2 1 3 1 4 1 5	0 1 4 0 4