You are given a rooted tree with N vertices, numbered from 1 to n, the root is 1.
The weight of edges is 1, the value of vertices is 0 at the beginning.
There are 3 type of operation:
1 x : query the value of vertex x
2 x y : modify the weight of edge to y whose child node is x
3 x y : for every vertex i in the tree, value of it add ($y \cdot dis(x , i)$),
$dis(x , i)$ means the shortest distance between x and i in tree
Input
The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer N : the size of the tree.
The next one line contains N-1 integers, ith number Pi denotes there is an edge between i+1 and Pi.
The next line contains one integer M : times of operation.
The next M line, each line contains one operation mentioned above.
Limits
$T \leq 10$
$2 \leq N \leq 100000$
$0 \leq M \leq 200000$
$1 \leq Pi \leq i$ , for $1 \leq i < N$
operation 1 : $1 \leq x \leq N$
operation 2 : $2 \leq x \leq N$ , $1 \leq y \leq 100$
operation 3 : $1 \leq x \leq N$ , $1 \leq y \leq 100$
Output
For each operation 1 output one integer denotes the answer.