Through Path

We have a tree with $N$ vertices and $N-1$ edges, where the vertices are numbered $1, 2, \dots, N$ and the edges are numbered $1, 2, \dots, N-1$. Edge $i$ connects Vertices $a_i$ and $b_i$. Each vertex in the tree has an integer written on it. Let $c_i$ be the integer written on Vertex $i$. Initially, $c_i = 0$. You will be given $Q$ queries. The $i$\-th query, consisting of integers $t_i$, $e_i$, and $x_i$, is as follows: * If $t_i = 1$: for each Vertex $v$ reachable from Vertex $a_{e_i}$ without visiting Vertex $b_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$. * If $t_i = 2$: for each Vertex $v$ reachable from Vertex $b_{e_i}$ without visiting Vertex $a_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$. After processing all queries, print the integer written on each vertex. ## Constraints * All values in input are integers. * $2 \le N \le 2 \times 10^5$ * $1 \le a_i, b_i \le N$ * The given graph is a tree. * $1 \le Q \le 2 \times 10^5$ * $t_i \in {1, 2}$ * $1 \le e_i \le N-1$ * $1 \le x_i \le 10^9$ ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$ $Q$ $t_1$ $e_1$ $x_1$ $\vdots$ $t_Q$ $e_Q$ $x_Q$ [samples]