题目描述

利用拉米留下的大自在式，夏娜与悠二需要使用巨大的存在之力来修复残破不堪的御崎市。拉米在御崎市部下了 N 个容器，每个容器各承载了一定量的存在之力，并连接成了一 个树形结构。夏娜可以选择树上的一条包含了奇数个容器简单路径施展大自在式；并且为了 存在之力的均衡，容器所承载的存在之力需要构成一个回文串。 夏娜想要知道选择的路径上存在之力之和的最大值是多少。作为天壤劫火阿拉斯多尔， 你需要帮助她解决这个问题。

输入格式

输入第 1 行一个整数 N 表示容器的个数。 输入第 2 行有 N 个整数，第 𝑖 个整数 𝑤𝑖 表示第 𝑖 个容器承载的存在之力的量。 输入接下来 N - 1 行每行两个整数 𝑢𝑖,𝑣𝑖，表示容器 𝑢𝑖 到容器 𝑣𝑖 有一个自在式连接。

输出

输出一行 N 个整数，第 𝑖 个数表示第 𝑖 个容器作为因果的十字路口时，能选择的路径上存在之力之和的最大值。

样例

Input

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

Output

9 2 1 4 1 1

数据范围

对于 100%的数据， 1 ≤ 𝑛 ≤ 3000,1 ≤ 𝑤𝑖 ≤ 109