题目内容

在一个偏远的山区里，有一个叫做塔子哥的数学家。他热爱数学，对树这种数据结构也有着浓厚的兴趣。

有一天，他在森林中漫步时发现了一棵美丽的大树。这棵树非常漂亮，每个节点 $i$ 都是独特的，有着它自己的权值 $val_i$ ，并且规定 $1$ 号点为这棵树的根节点。

塔子哥对这棵树产生了浓厚的兴趣，他开始研究这棵树的性质，并思考一些问题。他想知道如果对于树上的某个节点 $t$ ，以 $t$ 为根的子树中所有节点的权值都乘上一个 $g$ ，会对整棵树产生什么影响。

为了更好地研究这个问题，他进行了 $q$ 次操作，每次选择了一个节点 $t$ ，并将以 $t$ 为根的子树中所有节点的权值都乘上了一个 $g$ 。这个过程中，他记录了每个节点的最终权值，但他还想知道一个更有趣的问题：在 $q$ 次操作结束以后，以节点 $i$ 为根的子树中所有节点的权值的乘积的末尾有多少个0。

这个问题非常有趣，因为它不仅涉及到树的结构，还需要考虑数学中数字的性质。塔子哥非常期待你能帮他解决这个问题。

输入描述

第一行输入一个正整数$n$，代表这颗树的节点的数量。

第二行输入$n$个正整数$val_i$，代表每个节点的权值。

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

接下来的一行输入一个正整数$q$，代表操作次数。

接下来的$q$行，每行输入两个正整数$t$和$g$，代表塔子哥的一次操作。

$1 \leqslant n,q \leqslant 10^5$

$1 \leqslant v_i,g \leqslant 10^9$

$1 \leqslant t,u,v \leqslant n$

输出描述

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

样例

输入

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

输出

4 1 0 2 0 1