시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 8 4 4 50.000%

문제

There is a rooted tree. Each vertex contains some non-negative amount of charge cv. You have to process three kinds of queries:

  • Move the charge up: all vertices simultaneously transfer all their charge to their direct parent. The charge from the root is not transferred anywhere. That is, if vertex v had children u1, . . . , uk, then its new charge becomes cu1 + . . . + cuk for a non-root vertex v, or cu1 + . . . + cuk + cv if v is the root.
  • Move the charge down: all vertices simultaneously transfer all their charge to their children in equal proportions. That is, if vertex v had children u1, . . ., uk, then the new charge of each ui becomes cv/k.
    There is a virtual line tree of sufficient length attached to each leaf. That is, if the charge is moved down from the leaf and then moved up the same number of times, then the leaf retains its original charge.
  • Add charge to a vertex: add a certain amount of charge to a certain vertex.

At the end, you should print the value of charge in each vertex.

입력

In the first line of input there is a single integer n, the number of vertices in the tree (2 ≤ n ≤ 500 000).

The next line contains n integers ci, i-th of them denoting the initial charge of the tree (0 ≤ ci < 109 + 7).

Each of the next n − 1 lines contains two integers ui and vi denoting the edge between vertices ui and vi (1 ≤ ui, vi ≤ n).

Next line contain a single integer q, the number of queries (0 ≤ q ≤ 500 000). Then q lines follow with the description of queries. “Move up” query is denoted with a character “ˆ”. “Move down” query is denoted with a character “v”. “Add charge” query is denoted with a character “+” followed by two integers vi and xi, meaning that you should add charge xi to vertex vi (1 ≤ vi ≤ n, 0 ≤ xi < 109 + 7).

It is guaranteed that the graph in the input is a tree.

출력

Print n numbers, i-th of them being the final charge of vertex i modulo 109 + 7.

Formally, let the charge be p/q. Then you should print a unique number x, 0 ≤ x < 109 + 7, such that p ≡ x · q mod 109 + 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