Description

在百字节森林的中央，生长着一棵奇特的树，住着会咆哮的蜗牛。这棵树共有 $n$ 个顶点，编号为 $1$ 到 $n$，并且通过 $n-1$ 条边连接，形成一棵连通图。最初，每个顶点上最多只有一只雄性蜗牛。

某一时刻，一只雌性蜗牛出现在树上的某个顶点，并开始咆哮。每当雌性蜗牛咆哮一次，有一只雄性蜗牛会沿着边向它靠近一步。但若目标顶点上已经有另一只雄性蜗牛，或该雄性蜗牛已与雌性蜗牛处于同一顶点，则它不能移动。当所有雄性蜗牛都无法再移动时，雌性蜗牛停止咆哮。

给定这棵树的结构以及每个顶点上是否有雄性蜗牛的信息，请对于每个顶点，计算若雌性蜗牛出现在该顶点时，最多能咆哮多少次。假设雄性蜗牛会以使咆哮次数最大的方式移动。

Format

Input

第一行包含一个整数 $n$（$1 \le n \le 2\times10^5$），表示树中顶点的数量。

第二行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1：

• 若第 $i$ 个字符为 1，表示顶点 $i$ 上有一只雄性蜗牛；
• 若为 0，则该顶点上没有雄性蜗牛。

接下来 $n-1$ 行，每行包含两个整数 $a_i, b_i$（$1 \le a_i, b_i \le n$，且 $a_i \ne b_i$），表示顶点 $a_i$ 与 $b_i$ 之间有一条边。

Output

输出 $n$ 个整数，第 $i$ 个整数表示如果雌性蜗牛出现在第 $i$ 个顶点上，她最多能咆哮的次数。

Samples

5
10101
1 2
2 3
2 4
4 5

2 2 2 3 3

Note

下图展示了样例中的树结构。灰色的顶点表示有雄性蜗牛的位置。