Problem Description

You are given a rooted tree with edge weight $1$ and root at node $1$. Each node has a node value initially equal to $0$. The distance between two nodes is defined as the length of the simple path between them in the tree. You need to support two types of operations:

1 a x y z: For all nodes in the subtree of $a$ whose distance to $a$ modulo $x$ equals $y$, add $z$ to their node values.

2 a: Query the node value of node $a$.

Input Format

The first line contains two integers $n, m$, meaning the tree has $n$ nodes and there are $m$ operations.

The second line contains $n - 1$ integers. The $i$-th integer $f_i$ denotes the parent of node $i + 1$ in the tree.

Then follow $m$ lines, each in the form 1 a x y z or 2 a, representing the operations above.

Output Format

For each operation of type $2$, output one line with one integer representing the answer.

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

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

Constraints: For $100\%$ of the testdata, $1\leq n, m\leq 3\times 10^5$, $1\leq f_i\leq i$, $1\leq a\leq n$, $1\leq x\leq n$, $0\leq y < x$, $0 \leq z < 514$.

Translated by ChatGPT 5