Let me come straight to the question:

There are t test cases. For each test case -

You are given a tree consisting of n nodes labelled from 1 to n (each node has unique label), each node has value node[i] in it. Now, you are given q1 queries of the form u,v,k where it is guaranteed that u is an ancestor of v and you are supposed to add k to the value of each node on the path from u to v (including u and v). After answering all the q1 queries, print the values of all the nodes in the order 1 to n on a single line.

After that, you are given q2 queries of the type u,v where it is guaranteed that u is an ancestor of v and you need to print the sum of values of all nodes on the path from u to v (including u and v).

Print the answer to each of the q2 queries on a single line containing q2 space separated integers.

NOTE:

Root of the tree is the node whose parent is 0. (0 is just a dummy value, and should not be considered as a node).

Each node can have any number of children. But each node has exactly one parent (Except the root which has no parent).

Ancestor is a node reachable by repeated proceeding from child to parent. Thus root is the ancestor of all nodes.

IMPORTANT: Every node is also an ancestor of itself.

CONSTRAINTS:

1<=t<=10

1<=n<=200000

1<=q1+q2<=2 * 10^6

q2>=1

0<=node[i]<=10^9

0<=k<=100000

1<=u,v<=n

INPUT:

The first line contains a single integer t, denoting the number of test cases.

For each test case -

The first line contains a single integer n denoting the number of nodes in the tree.

The next line contains n space separated integers denoting node[i].

The next line contains n space separated integers where the ith integer parent[i] is the parent of node i.

For exactly one i, parent[i]=0. This means that node i is the root (SEE NOTE ABOVE).

The next line contains a single integer q1 denoting the number of queries of the form u,v,k as described above.

The next q1 lines contain exactly 3 space separated integers u,v,k.

The next line contains a single integer q2 denoting the number of queries of the form u,v as described above.

The next q2 lines contain exactly 2 space separated integers u,v.

OUTPUT:

Each test case should consist of 2 lines of output. For each test case -

The first line should consist of n space separated integers node[i] denoting the node values after answering all the q1 queries of the type u,v,k.

The second line should consists of q2 space separated integers, the ith integer denotes the answer to the ith query of type u,v as described above.

Problem Author : Viral Mehta