You are given a rooted tree with $n$ nodes, rooted at $1$, where each edge has a weight of $1$. Each node has an initial value of $0$. The distance between two nodes is defined as the length of the simple path between them in the tree. You need to support the following two operations:

1 a x y z: Add $z$ to the values of all nodes in the subtree of $a$ whose distance from $a$ is congruent to $y$ modulo $x$.

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

Input

The first line contains two integers $n$ and $m$, representing the number of nodes in the tree and the number of operations, respectively.

The second line contains $n-1$ integers, where the $i$-th integer $f_i$ represents the parent of node $i+1$.

The following $m$ lines each contain an operation of the form 1 a x y z or 2 a, as described above.

Output

For each 2 operation, output a single integer representing the answer on a new line.

Examples

Input 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

Output 1

5
0

Subtasks

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

For $100\%$ of the data, $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$, and $0 \leq z < 514$.