ADDAP - An easy Problem

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

Added by:ashish kumar
Date:2016-03-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:self

hide comments
2016-03-18 02:42:00 [Rampage] Blue.Mary
An (almost same) problem already exists: problem code INS14L.
-----> I have no idea ,that this problem exists but it seem my problem is lot more easier than that one. Also I can see that you overkill the problem by using segment tree . It can be done in very easy way with very few lines of code.


Last edit: 2016-03-18 15:05:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.