有一个包含 $N$ 个顶点的有根树，顶点编号从 $1$ 到 $N$。顶点 $1$ 是树的根，对于所有 $2 \le i \le N$，$P_i$ 是顶点 $i$ 的父节点。每个顶点都有一个初始值为 $0$ 的美观度（beautiness value）。

你可以使用一台特殊机器来增加顶点的美观度。通过向机器输入三个参数 $X$、$Y$ 和 $K$，机器会增加顶点 $X$ 子树中所有顶点的美观度。如果顶点 $X'$ 在顶点 $X$ 的子树中，那么它的美观度将增加 $\lfloor \frac{Y}{K^d} \rfloor$，其中 $d$ 是连接顶点 $X$ 到顶点 $X'$ 的路径上的边数。例如，顶点 $X$ 的美观度将增加 $Y$，顶点 $X$ 的所有子节点的美观度将增加 $\lfloor \frac{Y}{K} \rfloor$，顶点 $X$ 的子节点的子节点的美观度将增加 $\lfloor \frac{Y}{K^2} \rfloor$，以此类推。

你将依次执行 $Q$ 次操作。每次操作属于以下类型之一：

1. 使用特殊机器，输入参数 $X$、$Y$ 和 $K$。
2. 查询顶点 $X$ 子树中所有顶点的美观度总和。

对于每种第二类型的操作，输出顶点 $X$ 子树中所有顶点的美观度总和。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 100\,000$)，分别表示顶点数量和操作数量。下一行包含 $N-1$ 个整数：$P_i$ ($1 \le P_i < i$)，表示顶点 $i \in [2, N]$ 的父节点；注意 $i$ 从 $2$ 开始。接下来的 $Q$ 行，每行包含以下格式之一的操作：

• 1 X Y K ($1 \le X \le N; 1 \le Y, K \le 100\,000$) 使用特殊机器，输入参数 $X$、$Y$ 和 $K$。
• 2 X ($1 \le X \le N$) 输出顶点 $X$ 子树中所有顶点的美观度总和。

保证至少会进行一次第二类型的操作。

输出格式

对于每个第二类型的操作，按输入顺序输出一行，包含一个整数，表示顶点 $X$ 子树中所有顶点的美观度总和。

样例

样例输入 1

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

样例输出 1

245
97
99

说明 1

树的结构如下图所示：

• 第一次操作将顶点 $1$ 的美观度增加了 $99$，顶点 $2$ 和 $3$ 的美观度增加了 $49$，顶点 $4$ 和 $5$ 的美观度增加了 $24$。
• 顶点 $1$ 子树中所有顶点的美观度总和为 $99 + 49 + 49 + 24 + 24 = 245$。
• 顶点 $3$ 子树中所有顶点的美观度总和为 $49 + 24 + 24 = 97$。
• 第四次操作将顶点 $3$ 的美观度增加了 $2$，顶点 $4$ 和 $5$ 的美观度增加了 $0$。
• 顶点 $3$ 子树中所有顶点的美观度总和为 $51 + 24 + 24 = 99$。