给定一棵有根树。每个顶点包含一些非负电荷 $c_v$。你需要处理三种类型的查询：

• 向上移动电荷：所有顶点同时将其所有电荷转移给它们的直接父节点。根节点的电荷不会转移到任何地方。也就是说，如果顶点 $v$ 有子节点 $u_1, \dots, u_k$，那么对于非根节点 $v$，其新电荷变为 $c_{u_1} + \dots + c_{u_k}$；如果 $v$ 是根节点，其新电荷变为 $c_{u_1} + \dots + c_{u_k} + c_v$。
• 向下移动电荷：所有顶点同时将其所有电荷按比例平均转移给它们的子节点。也就是说，如果顶点 $v$ 有子节点 $u_1, \dots, u_k$，那么每个 $u_i$ 的新电荷变为 $c_v/k$。每个叶子节点下方都连接着一条足够长的虚拟线树。这意味着，如果电荷从叶子节点向下移动，然后再向上移动相同次数，则叶子节点将保留其原始电荷。
• 增加顶点电荷：向某个顶点增加一定量的电荷。

最后，你需要输出每个顶点的电荷值。

输入格式

输入的第一行包含一个整数 $n$，表示树的顶点数 ($2 \le n \le 500\,000$)。 下一行包含 $n$ 个整数 $c_i$，其中第 $i$ 个数表示树的初始电荷 ($0 \le c_i < 10^9 + 7$)。 接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 和 $v_i$ 之间的边 ($1 \le u_i, v_i \le n$)。 下一行包含一个整数 $q$，表示查询次数 ($0 \le q \le 500\,000$)。随后是 $q$ 行查询描述。“向上移动”查询用字符 “^” 表示。“向下移动”查询用字符 “v” 表示。“增加电荷”查询用字符 “+” 后跟两个整数 $v_i$ 和 $x_i$ 表示，意味着你应该向顶点 $v_i$ 增加电荷 $x_i$ ($1 \le v_i \le n, 0 \le x_i < 10^9 + 7$)。

保证输入图是一棵树。

输出格式

输出 $n$ 个数字，第 $i$ 个数字表示顶点 $i$ 的最终电荷对 $10^9 + 7$ 取模的结果。 形式上，设电荷为 $p/q$。你需要输出一个唯一的整数 $x$，$0 \le x < 10^9 + 7$，使得 $p \equiv x \cdot q \pmod{10^9 + 7}$。

样例

样例输入 1

5
4 3 3 6 0
1 2
1 3
2 4
4 5
5
v
+ 1 7
^
+ 2 1
v

样例输出 1

0 500000009 500000009 4 6

样例输入 2

2
5 10
1 2
5
v
v
v
^
^

样例输出 2

0 5

样例输入 3

4
0 1 0 0
1 2
1 3
1 4
2
^
v

样例输出 3

0 333333336 333333336 333333336