Subtree Update and Query on a Rooted Tree

You are given a rooted tree with n nodes numbered from 1 to n with the root being node 1. Each edge has a weight of 1 and every node has an initial weight of 0. The distance between two nodes is defined as the number of edges in the unique simple path between them. You need to support the following two types of operations:

• 1 a x y z: For every node u in the subtree of node a (including a), if \[ (\mathit{depth}(u) - \mathit{depth}(a)) \bmod x = y, \] then add z to the weight of node u.
• 2 a: Output the current weight of node a.

The tree structure is provided as follows: The first line of input contains two integers n and q, representing the number of nodes and the number of operations respectively. The second line contains n - 1 integers, where the i-th integer (for i = 2, 3, \dots, n) denotes the parent of node i. Then q lines follow, each representing an operation in the format described above.

Note: The depth of a node is defined as the distance from the root (with depth(1)=0), therefore for any node u in the subtree of a, the value depth(u) - depth(a) denotes its distance from a.

inputFormat

The input begins with a line containing two integers n and q — the number of nodes in the tree and the number of queries respectively.

The next line contains n - 1 integers, where the i-th integer (for i = 2, 3, \dots, n) is the parent of node i.

Each of the following q lines contains an operation in one of the following formats:

• 1 a x y z — update operation, where for every node u in the subtree of a such that \( (\mathit{depth}(u)-\mathit{depth}(a)) \bmod x = y \), add z to its weight.
• 2 a — query operation that asks for the current weight of node a.

outputFormat

For each operation of type 2 a, output the weight of node a on a new line.

sample

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

0
0
8