题目描述

z2333 在 AK 了 UOI 之后，打算去 AK YOI。

但邪恶的 RQAQ 不打算让 z2333 AK YOI，因为这届 YOI 的题全部都是由 RQAQ 出的。

于是 RQAQ 用化学铁来让 z2333 丧失秒切题的能力。

但 z2333 发现自己只要花 $1$ 分钟去切一道题后，他便能恢复秒切题的能力。

这个题的题目描述如下：

给定一棵树，同时给定一对 $L,R$，对于每一个点，求出所有经过这个点，且边数在 $[L,R]$ 的路径中，路径上点权和最大的那个点权和。

即对于每个点 $u$，需要求出：

$$ \Large fu=\max \sum{p \in (x,y)} v_p $$

其中满足：

1. $(x,y)$ 是一条经过 $u$ 的简单路径；
2. $L \le |(x,y)| \le R$。

当然了，路径的端点也是要算上的。

如果你解决了这道题，z2333 会十分高兴，他会让 z6666 来传授给你如何玩玻璃球。

输入格式

第一行三个整数 $n, L, R$；

第二行 $n$ 个整数，表示 $v_i$；

之后有 $n - 1$ 行，每行两个整数 $x, y$ 表示有一条连接着 $x,y$ 的边。

输出格式

输出一行 $n$ 个整数，分别表示 $f_i$；

如果无解，输出 $-3472328296227680305$。

样例

input

5 1 3
-1 -6 7 7 4
1 2
2 3
3 4
4 5

output

7 12 18 18 18

数据范围与提示

对于全部数据，$1 \le n,x_i,y_i \le 10^5,0 \le |v_i| \le 10^5,1 \le L \le R \le n$。