An easy Problem
Problem Statement
Seeing so much companies coming for placement in ISM, **BABBU** also started coding. After rigorous coding for two months , he got bored in solving problems . Now he wants to become problem setter. In order to set problems he took advice from his friends **GOTU** and **CHHOTU**.
After having a heavy discussion they came up with a problem which goes like this.....
You are given a tree rooted at **1**.<br>
And you are given **Q** number of queries to perform on tree. <br>
For each query you are given $u$, $x$ and $y$, where $u$ denotes the node number. <br>
You have to add value $x$ to the node $u$, $x+y$ to its all children at depth $1$(one), x+2y to all its children at depth 2, .. , $x + d*y$ to all its children at depth $d$ and so on.
Seeing so much companies coming for placement in ISM, BABBU also started coding. After rigorous coding for two months , he got bored in solving problems . Now he wants to become problem setter. In order to set problems he took advice from his friends GOTU and CHHOTU.
After having a heavy discussion they came up with a problem which goes like this.....
You are given a tree rooted at 1.
And you are given Q number of queries to perform on tree.
For each query you are given u, x and y, where u denotes the node number.
You have to add value x to the node u, x+y to its all children at depth 1(one), x+2y to all its children at depth 2, .. , x + d*y to all its children at depth d and so on.
Input Format
First line of input contains N ( total number of nodes in tree).
Next N-1 lines contain u and v .
i.e there is and edge between u and v.
Next line contains a single integer Q , indicating total number of queries to perform on tree.
Next Q lines contain u x y.
1<=N <=100000
1<=u <= N
1<=x, y <=100000
1<=Q<=100000
Output Format
You have to output final values of each node from 1 to N after performing Q queries.
Since values may be large print it modulo 1000000007
Sample Input
10
4 9
6 4
7 10
5 3
2 6
1 5
5 10
3 8
7 2
5
7 8 1
1 10 7
7 4 7
1 4 1
4 9
6 4
7 10
5 3
2 6
1 5
5 10
3 8
7 2
5
7 8 1
1 10 7
7 4 7
1 4 1
2 6 2
Sample Output
14
72
30
108
22
90
50
38
126
30
72
30
108
22
90
50
38
126
30