Vasya has a tree consisting of n vertices with root in vertex 1. At first all vertices has 0 written on it.

Let d(i, j) be the distance between vertices i and j, i.e. number of edges in the shortest path from i to j. Also, let's denote k-subtree of vertex x — set of vertices y such that next two conditions are met: 

  * x is the ancestor of y (each vertex is the ancestor of itself); 
  * d(x, y) ≤ k. 



Vasya needs you to process m queries. The i-th query is a triple v_i, d_i and x_i. For each query Vasya adds value x_i to each vertex from d_i-subtree of v_i.

Report to Vasya all values, written on vertices of the tree after processing all queries.

Input

The first line contains single integer n (1 ≤ n ≤ 3 ⋅ 10^5) — number of vertices in the tree.

Each of next n - 1 lines contains two integers x and y (1 ≤ x, y ≤ n) — edge between vertices x and y. It is guarantied that given graph is a tree.

Next line contains single integer m (1 ≤ m ≤ 3 ⋅ 10^5) — number of queries.

Each of next m lines contains three integers v_i, d_i, x_i (1 ≤ v_i ≤ n, 0 ≤ d_i ≤ 10^9, 1 ≤ x_i ≤ 10^9) — description of the i-th query.

Output

Print n integers. The i-th integers is the value, written in the i-th vertex after processing all queries.

Examples

Input


5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100


Output


1 11 1 100 0 


Input


5
2 3
2 1
5 4
3 4
5
2 0 4
3 10 1
1 2 3
2 3 10
1 1 7


Output


10 24 14 11 11 

Note

In the first exapmle initial values in vertices are 0, 0, 0, 0, 0. After the first query values will be equal to 1, 1, 1, 0, 0. After the second query values will be equal to 1, 11, 1, 0, 0. After the third query values will be equal to 1, 11, 1, 100, 0.
import java.io.*;
import java.util.*;
import java.lang.*;

public class curr {
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static long MOD = (long) (1e9 + 7);
    //    static int MOD = 998244353;
    static long MOD2 = MOD * MOD;
    static FastReader sc = new FastReader();
    static int pInf = Integer.MAX_VALUE;
    static int nInf = Integer.MIN_VALUE;
    static long ded = (long)(1e17)+9;
    public static void main(String[] args) throws Exception {
        int test = 1;
//        test = sc.nextInt();
        for (int i = 1; i <= test; i++){
//            out.print("Case #"+i+": ");
            solve();
        }
        out.flush();
        out.close();
    }
    static int n,q;
    static ArrayList<Integer> A[];
    static ArrayList<Pair>[] Q;
    static long[] add,result;
    static void solve()throws Exception{
        n = sc.nextInt();
        A = new ArrayList[n+1];
        Q = new ArrayList[n+1];
        add = new long[n+5];
        result = new long[n+5];
        for(int i = 1; i <= n; i++){
            A[i] = new ArrayList<>();
            Q[i] = new ArrayList<>();
        }
        for(int i = 1; i < n; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            A[u].add(v);
            A[v].add(u);
        }
        q = sc.nextInt();
        while(q-->0){
            int u = sc.nextInt();
            int dis = sc.nextInt();
            int val = sc.nextInt();
            Q[u].add(new Pair(dis,val));
        }
        dfs(1,0,0,0);
        for(int i = 1; i <= n; i++){
            out.print(result[i]+" ");
        }
        out.println();
    }
    static void dfs(int u,int pu,int depth,long sum){
        for(Pair p: Q[u]){
            int l = depth;
            int r = depth+p.x;
            add[l] += p.y;
            if(r+1<add.length){
                add[r+1] -= p.y;
            }
        }
        sum += add[depth];
        result[u] = sum;
        for(int v: A[u]){
            if(v==pu){
                continue;
            }
            dfs(v,u,depth+1,sum);
        }
        for(Pair p: Q[u]){
            int l = depth;
            int r = depth+p.x;
            add[l] -= p.y;
            if(r+1<add.length){
                add[r+1] += p.y;
            }
        }
    }
    static class Pair implements Comparable<Pair> {
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
//            this.idx = idx;
        }
        @Override
        public int compareTo(Pair o){
            if(this.y==o.y){
                return this.x-o.x;
            }
            return this.y-o.y;
        }
    }
    public static long mul(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }
    public static long add(long a, long b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    public static long c2(long n) {
        if ((n & 1) == 0) {
            return mul(n / 2, n - 1);
        } else {
            return mul(n, (n - 1) / 2);
        }
    }
    //Shuffle Sort
    static final Random random = new Random();
    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n); int temp= a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }
    //Brian Kernighans Algorithm
    static long countSetBits(long n) {
        if (n == 0) return 0;
        return 1 + countSetBits(n & (n - 1));
    }
    //Euclidean Algorithm
    static long gcd(long A, long B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }
    //Modular Exponentiation
    static long fastExpo(long x, long n) {
        if (n == 0) return 1;
        if ((n & 1) == 0) return fastExpo((x * x) % MOD, n / 2) % MOD;
        return ((x % MOD) * fastExpo((x * x) % MOD, (n - 1) / 2)) % MOD;
    }
    //AKS Algorithm
    static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i <= Math.sqrt(n); i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }
    public static long modinv(long x) {
        return modpow(x, MOD - 2);
    }
    public static long modpow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        long x = modpow(a, b / 2);
        x = (x * x) % MOD;
        if (b % 2 == 1) {
            return (x * a) % MOD;
        }
        return x;
    }

    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException{
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() {
            try{
                byte[] buf = new byte[10000000]; // line length
                int cnt = 0, c;
                while ((c = read()) != -1) {
                    if (c == '\n')
                        break;
                    buf[cnt++] = (byte) c;
                }
                return new String(buf, 0, cnt);
            }catch (Exception e){
                System.out.println(e.getMessage());
                return null;
            }
        }

        public int nextInt()  {
            int ret = 0;
            try {
                byte c = read();
                while (c <= ' ')
                    c = read();
                boolean neg = (c == '-');
                if (neg) c = read();
                do{
                    ret = ret * 10 + c - '0';
                }  while ((c = read()) >= '0' && c <= '9');

                if (neg) return -ret;
                return ret;
            } catch (Exception e) {
                System.out.println(e.getMessage());
                return -1;
            }
        }

        public long nextLong()   {

            try {
                long ret = 0;
                byte c = read();
                while (c <= ' ') c = read();
                boolean neg = (c == '-');
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                }
                while ((c = read()) >= '0' && c <= '9');
                if (neg)
                    return -ret;
                return ret;
            } catch (Exception e) {
                System.out.println(e.getMessage());
                return -1;
            }
        }

        public double nextDouble()  {

            try {
                double ret = 0, div = 1;
                byte c = read();
                while (c <= ' ')
                    c = read();
                boolean neg = (c == '-');
                if (neg) c = read();

                do {
                    ret = ret * 10 + c - '0';
                }
                while ((c = read()) >= '0' && c <= '9');
                if (c == '.') {
                    while ((c = read()) >= '0' && c <= '9') {
                        ret += (c - '0') / (div *= 10);
                    }
                }

                if (neg) return -ret;
                return ret;
            } catch (Exception e) {
                System.out.println(e.getMessage());
                return -1;
            }
        }

        private void fillBuffer() throws IOException{
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException  {
            try{
                if (bufferPointer == bytesRead)
                    fillBuffer();
                return buffer[bufferPointer++];
            }catch(Exception e){
                System.out.println(e.getMessage());
                return -1;
            }
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
}