Tree Beauty

A rooted tree has N vertices numbered from 1 to N. Vertex 1 is the root, and $P_i$ is the parent of vertex $i$ for all $2 \le i \le N$. Each vertex has a beautiness value, which starts at 0.

A special machine increases the beautiness values of vertices. When you give the machine three parameters X, Y, and K, it increases the beautiness value of every vertex in the subtree of vertex X. If vertex $X'$ is in the subtree of vertex X, its beautiness value increases by $\lfloor Y/K^d \rfloor$, where d is the number of edges on the path from X to $X'$. For example, vertex X increases by Y, the children of X increase by $\lfloor Y/K \rfloor$, the children of those children increase by $\lfloor Y/K^2 \rfloor$, and so on.

You perform Q operations one at a time. Each operation is one of the following two types.

1. Use the machine with parameters X, Y, and K.
2. Report the total beautiness value of all vertices in the subtree of vertex X.

The first line contains two integers N and Q ($1 \le N, Q \le 100\,000$), the number of vertices and the number of operations. The next line contains N - 1 integers $P_i$ ($1 \le P_i < i$), the parent of each vertex $i \in [2, N]$. Each of the next Q lines is one of the following.

• 1 X Y K ($1 \le X \le N$; $1 \le Y, K \le 100\,000$): use the machine with parameters X, Y, and K.
• 2 X ($1 \le X \le N$): report the total beautiness value of the subtree of vertex X.

For each operation of the second type, in the order given in the input, output on its own line the total beautiness value of all vertices in the subtree of vertex X.