在百字节森林（Hundred Bytes Wood）的中央生长着一棵不同寻常的树，树上栖息着会咆哮的蜗牛。这棵树由 $n$ 个顶点组成，编号从 $1$ 到 $n$，它们通过 $n-1$ 条边连接成一棵连通图。起初，树的每个顶点上最多有一只雄性咆哮蜗牛。

某一时刻，一只雌性蜗牛会出现在树的某个顶点上并开始咆哮。雌性蜗牛每咆哮一次，就有一只雄性蜗牛会沿着边向靠近雌性蜗牛的相邻顶点移动。然而，如果目标顶点已经有另一只雄性蜗牛，或者雄性蜗牛已经与雌性蜗牛处于同一顶点，则该雄性蜗牛无法移动。如果下一次咆哮后没有任何雄性蜗牛能够移动，雌性蜗牛就会停止咆哮。

给定栖息着咆哮蜗牛的树的描述。对于每个顶点，你还会获得关于该顶点是否有雄性蜗牛的信息。请计算如果雌性蜗牛位于某个顶点，她最多能咆哮多少次。我们假设雄性蜗牛的移动方式是使咆哮次数最大化。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示树的顶点数。

第二行包含一个由 $n$ 个字符 '0' 和 '1' 组成的字符串。如果第 $i$ 个字符为 '1'，则表示树的第 $i$ 个顶点上有一只雄性蜗牛。如果第 $i$ 个字符为 '0'，则表示树的第 $i$ 个顶点上没有雄性蜗牛。

接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)，表示树的顶点 $a_i$ 和 $b_i$ 之间有一条边。

输出格式

输出一行，包含 $n$ 个整数；第 $i$ 个整数表示如果雌性蜗牛位于第 $i$ 个顶点，她所能进行的最大咆哮次数。

样例

输入 1

5
10101
1 2
2 3
2 4
4 5

输出 1

2 2 2 3 3

说明

样例测试中的树如下图所示。雄性蜗牛位于阴影顶点中。

如果雌性蜗牛在第一个顶点，她最多可以咆哮两次，例如先吸引第三个顶点的雄性蜗牛到第二个顶点，然后吸引第五个顶点的雄性蜗牛到第四个顶点：

如果雌性蜗牛在第四个顶点，只要第五个顶点的雄性蜗牛不移动，她最多可以咆哮三次：