Influence

Problem 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

Source

2017 Multi-University Training Contest - Team 6

https://acm.hdu.edu.cn/showproblem.php?pid=6104