Tree of Charge

A rooted tree is given. Each vertex $v$ holds a non-negative charge $c_v$. You must process three kinds of queries.

• Move the charge up: all vertices simultaneously move their entire charge to their direct parent. The charge at the root is not moved anywhere. In other words, if vertex $v$ has children $u_1, \ldots, u_k$, then its new charge is $c_{u_1} + \cdots + c_{u_k}$ when $v$ is not the root, and $c_{u_1} + \cdots + c_{u_k} + c_v$ when $v$ is the root.
• Move the charge down: all vertices simultaneously split their charge equally among their children. If vertex $v$ has children $u_1, \ldots, u_k$, then the new charge of each $u_i$ is $c_v / k$. Each leaf has a virtual straight line tree of sufficient length attached to it. So if you move the charge down from a leaf and then move it up the same number of times, the leaf keeps its original charge.
• Add charge: add $x_i$ to the charge of vertex $v_i$.

After processing all queries, print the charge of every vertex.

The first line contains the number of vertices $n$ ($2 \le n \le 500\,000$). The second line contains the initial charges $c_i$ ($0 \le c_i < 10^9 + 7$). Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$, an edge of the tree ($1 \le u_i, v_i \le n$). The input graph is guaranteed to be a tree.

The next line contains the number of queries $q$ ($0 \le q \le 500\,000$). Each of the next $q$ lines is one query. A move up query is written as ^. A move down query is written as v. An add charge query is written as + followed by two integers $v_i$ and $x_i$, meaning add charge $x_i$ to vertex $v_i$ ($1 \le v_i \le n$, $0 \le x_i < 10^9 + 7$).

Print $n$ numbers. The $i$-th number is the final charge of vertex $i$.

Let the charge be the fraction $p/q$. Print the unique integer $x$ with $0 \le x < 10^9 + 7$ such that $p \equiv x \cdot q \pmod{10^9 + 7}$.