트리 위의 전하

루트가 있는 트리가 주어진다. 각 정점 $v$에는 음이 아닌 전하 $c_v$가 들어 있다. 다음 세 종류의 쿼리를 처리해야 한다.

• 전하를 위로 옮기기: 모든 정점이 동시에 자신의 전하 전체를 직접 부모에게 옮긴다. 루트의 전하는 어디로도 옮겨지지 않는다. 즉 정점 $v$의 자식이 $u_1, \ldots, u_k$라면, $v$가 루트가 아닐 때 새 전하는 $c_{u_1} + \cdots + c_{u_k}$이고, $v$가 루트이면 $c_{u_1} + \cdots + c_{u_k} + c_v$이다.
• 전하를 아래로 옮기기: 모든 정점이 동시에 자신의 전하를 자식들에게 같은 비율로 나눠 준다. 정점 $v$의 자식이 $u_1, \ldots, u_k$라면, 각 $u_i$의 새 전하는 $c_v / k$가 된다. 각 잎에는 길이가 충분한 가상의 직선 트리가 이어져 있다. 따라서 잎에서 전하를 아래로 내린 뒤 같은 횟수만큼 위로 올리면, 그 잎은 원래 전하를 그대로 유지한다.
• 전하 추가: 정점 $v_i$에 전하 $x_i$를 더한다.

모든 쿼리를 처리한 뒤 각 정점의 전하를 출력한다.

첫 줄에 정점 수 $n$이 주어진다 ($2 \le n \le 500\,000$). 둘째 줄에는 각 정점의 초기 전하 $c_i$가 주어진다 ($0 \le c_i < 10^9 + 7$). 이어지는 $n-1$개의 줄에는 간선 $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$의 최종 전하이다.

전하가 분수 $p/q$로 주어질 때, $0 \le x < 10^9 + 7$이고 $p \equiv x \cdot q \pmod{10^9 + 7}$을 만족하는 유일한 정수 $x$를 출력한다.