题目描述

ak机是一位著名的计算机科学家，在一次采集森林中的植物时，偶然发现了一棵非常特殊的树。这棵树是一棵二叉树，其节点上都标有不同的数字。

在细心观察后，ak机意识到这棵二叉树是由多个相同的子树组成的，每个子树的根节点都是同一个数字。他对这个发现感到非常兴奋，并且开始研究如何计算这些子树的价值。

他定义每个节点的价值为其子树节点乘积的末尾 $0$ 的数量。因此，如果一个节点的子树中有 $k$ 个数末尾带有 $0$，那么该节点的价值为 $k$。

ak机想编写一个程序来计算每个节点的价值，以便能够更好地研究这棵树的特性。他请求您的帮助来实现这个程序，您需要返回一棵二叉树，树的结构和给定的二叉树相同，将每个节点的权值替换为该节点的价值。

二又树节点数不超过 $10^5$ 。

二又树每个节点的权值都是不超过 $10^9$ 的正整数。

输入描述

第一行为一个整数 $n(1\le n \le 10^5)$ ，表示这棵树的节点个数。

第二行为 $n$ 个整数，第 $i$ 个整数为 $a_i(1\le a_i \le 10^9)$ ，表示这 $n$ 个节点的取值。

接下来的 $n−1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表节点 $u$ 和节点 $v$ 有一条边相连。 根为1

输出描述

输出一行 $n$ 个正整数，分别代表 $1$ 号节点到 $n$ 号节点，每个节点的子树权值乘积尾零的数量。

样例

输入

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

输出

3 2 1 0 0

说明