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

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 nodes 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

You have to output final values of each node from 1 to N after performing Q queries.

Since the values may be large print them 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
2 6 2

Output
14
72
30
108
22
90
50
38
126
30