 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Third qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Nick is a freshman. He studies trees in his Algorithms class. He studies polynomials in his Algebra class. And he likes to create and combine. He has recently come up with a problem he cannot solve. Help him!
You are given a rooted tree with n vertices, numbered from 1 to n. There is a value in each vertex, initially all values are equal to 0. For a vertex v let us denote as d[v] the depth of the vertex v — the number of vertices on a path from the root of the tree to v, in particular the root itself has depth equal to 1.
You are also given k. You must process queries of two types.
 You are given a vertex v and a polynomial q(t) = q_{0} + q_{1}t + q_{2}t^{2} + ... + q_{k}t^{k}. For each vertex u in a subtree of the vertex v you must add q(d[u]) to the value in that vertex.
 You are given a vertex v and a polynomial q(t) = q_{0} + q_{1}t + q_{2}t^{2} + ... + q_{k}t^{k}. For each vertex u on a path from the root of the tree to v, inclusive, add q(d[u]) to the value in that vertex.
All arithmetic operations are performed modulo 10^{9} + 7.
Help Nick to find the values in all vertices after all operations.
Input format 
Input data contains multiple test cases. The first line of input data contains integer t — the number of test cases (1 ≤ t ≤ 10^{5}). The description of test cases follow. Each description starts with two integers: n — the number of vertices in a tree, and k — the maximal degree of the polynomials (1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 20). The following n integers p_{1}, p_{2}, ..., p_{n} describe the tree, p_{i} is the number of a parent of the vertex i, or 0, if i is the root. It is guaranteed, that p_{i} describe the correct rooted tree. The integer q follows — the number of queries (1 ≤ q ≤ 10^{5}). The following q lines contain queries, each query is specified by an integer t, equal to 1 or 2 — the type of the query, followed by v — the vertex in the query, and then k + 1 integers q_{0}, q_{1}, ..., q_{k} — coefficients of the polynomial in the query (0 ≤ q_{i} < 10^{9} + 7). It is guaranteed that the sum of values of n in all test cases of one input data doesn't exceed 10^{5}. Similarly, the sum of values of q in all test cases of one input data doesn't exceed 10^{5}. 

Output format 
For each test case output n integers, for each vertex print the value in this vertex after all queries. Remember to perform all operations modulo 10^{9} + 7. 
Examples 
Input data
1 4 2 2 4 2 0 3 1 2 0 1 0 2 3 1 0 0 2 1 0 0 1
Output data
12 7 4 2 
