Jerry 有一个由 $n$ 个房间组成的网络，这些房间由 $n - 1$ 条双向通道连接，使得任意两个房间都是（直接或间接）连通的。每个房间里都有一定数量的奶酪。在房间 $i$（$1 \le i \le n$）中，奶酪的数量为 $c_i$。该网络在房间 $n$ 处有一个出口。

一只老鼠最初位于房间 1。在每一步中，老鼠会利用嗅觉探测相邻房间中的奶酪数量，并随机选择通过一条通道，其概率与对应房间中的奶酪数量成正比。老鼠永远不会考虑回到之前去过的房间。如果没有下一个通道可供选择，老鼠就会被困住。

Jerry 想要最大化老鼠到达出口的概率。为了做到这一点，他可以向任何房间添加奶酪。然而，他只能向每个房间添加整数数量的奶酪，且添加的总量不能超过 $x$。

Jerry 应该向每个房间添加多少奶酪，才能使老鼠逃脱的概率最大？

输入格式

输入的第一行包含两个整数 $n$（$2 \le n \le 200\,000$）和 $x$（$1 \le x \le 10^9$）。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$）。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示房间 $u_i$ 和 $v_i$ 之间有一条通道直接相连。

保证房间网络是连通的。此外，保证初始时所有房间中的奶酪总数不超过 $10^9$。

输出格式

输出 $n$ 个非负整数。第 $i$ 个整数表示 Jerry 应该向第 $i$ 个房间添加的奶酪数量。如果存在多个解，你可以输出其中任意一个。

样例

输入样例 1

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

输出样例 1

0 2 0 0 3

输入样例 2

3 3
1 2 3
1 2
2 3

输出样例 2

0 0 1