题目描述

There is a rooted tree of $N$ vertices, numbered from $1$ to $N$. Vertex $1$ is the root of the tree, while $P_i$ is the parent of vertex $i$, for all $2 \leq i \leq N$. Each vertex has a beautiness value, which is initially $0$.

You can use a special machine that can increase the beautiness value of the vertices. By giving three parameters $X$, $Y$, and $K$ to the machine, the machine will increase the beautiness value of all vertices in the subtree of vertex $X$. If vertex $X'$ is in the subtree of vertex $X$, then its beautiness value will increase by $\left\lfloor \frac{Y}{K^d} \right\rfloor$, where $d$ is the number of edges in the path connecting vertex $X$ to vertex $X'$. For example, the beautiness value of vertex $X$ will increase by $Y$, the beautiness value of all children of vertex $X$ will increase by $\left\lfloor \frac{Y}{K} \right\rfloor$, the beautiness value of all children of vertex $X$'s children will increase by $\left\lfloor \frac{Y}{K^2} \right\rfloor$, and so on.

You are going to perform $Q$ operations one by one. Each operation is one of the following types:

1. Use the special machine by giving three parameters $X$, $Y$, and $K$ to the machine.
2. Report the total beautiness value of all vertices in the subtree of vertex $X$.

For each operation of the second type, output the total beautiness value of all vertices in the subtree of vertex $X$.

输入格式

Input begins with a line containing two integers: $N\ Q$ ($1 \leq N, Q \leq 100\,000$) representing the number of vertices and the number of operations, respectively. The next line contains $N-1$ integers: $P_i$ ($1 \leq P_i < i$) representing the parent of vertices $i \in [2, N]$; note that $i$ starts from $2$. The next $Q$ lines each contains one of the following input format representing the operation you should perform.

• $1\ X\ Y\ K$ ($1 \leq X \leq N$; $1 \leq Y, K \leq 100\,000$)
  Use the special machine by giving three parameters $X$, $Y$, and $K$ to the machine.
• $2\ X$ ($1 \leq X \leq N$)
  Output the total beautiness value of all vertices in the subtree of vertex $X$.

There will be at least one operation of the second type.

输出格式

For each operation of the second type in the same order as input, output in a line an integer representing the total beautiness value of all vertices in the subtree of vertex $X$.

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

245
97
99

提示

Explanation for the sample input/output #1

The tree is illustrated by the following image.

:::align{center} :::

• The first operation increases the beautiness values of vertex $1$ by $99$, vertex $2$ and $3$ by $49$, and vertex $4$ and $5$ by $24$.
• The total beautiness value of all vertices in the subtree of vertex $1$ is $99 + 49 + 49 + 24 + 24 = 245$.
• The total beautiness value of all vertices in the subtree of vertex $3$ is $49 + 24 + 24 = 97$.
• The fourth operation increases the beautiness values of vertex $3$ by $2$ and vertex $4$ and $5$ by $0$.
• The total beautiness value of all vertices in the subtree of vertex $3$ is $51 + 24 + 24 = 99$.