# Influence

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

## Description

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.

## Sample Input

2
3
1 1
7
3 1 1
1 2
1 3
2 2 2
3 1 2
1 2
1 3
10
1 1 3 4 4 3 1 1 9
7
2 9 74
3 7 96
1 6
3 7 87
2 5 69
3 10 6
1 5

## Sample Output

1
1
5
3
288
1425

liuyiding

## Source

2017 Multi-University Training Contest - Te