Andy and Data Structure

Andy is a famous data structure expert at Nanjing University second to none. One day he throws a plain dry data structure problem to his friends, but none of them can solve. How about you?

Given a tree rooted at node 1. Each node has a weight which is 0 initially. Define the distance between two nodes as the number of edges in the unique simple path between the two nodes. You need to perform these two types of operations:

- Type 1: given $a, x, y, z$, add $z$ to the weights of all $a$'s descendants (including $a$ itself) whose distances to $a$ are $y$ modulo $x$;
- Type 2: given $a$, return the weight of node $a$.

The first line of the input is a single integer $T$ $(1 \leq T \leq 4)$, the number of test cases.

Each test cases starts with two integers $n, m$ $(1 \leq n, m \leq 300000)$, denoting that there are $n$ nodes (numbered $1$ through $n$) in the tree and you need to perform $m$ operations. The next line contains $n-1$ integers, $f_1, f_2, \cdots, f_{n-1}$ $(1 \leq f_i \leq i)$, specifying the edges of the trees; the $i$th integer denotes the parent of node $i+1$. The next $m$ lines describe the operations. Each line is either $\texttt{1 a x y z}$ $(1 \leq a \leq n, 1 \leq x \leq n, 0 \leq y < x, 0 \leq z \leq 500)$, denoting an operation of type 1, or $\texttt{2 a}$ $(1 \leq a \leq n)$, denoting an operation of type 2.

For each operation of type 2 in each test case, print the answer in one line.

1
5 5
1 1 2 1
1 1 5 4 1
1 1 4 1 5
1 2 1 0 4
2 3
2 1

5
0

2019 Multi-University Training Contest 8