题目描述

有一棵有根树，包含 $N$ 个顶点，编号从 $1$ 到 $N$。顶点 $1$ 是树的根，对于所有 $2 \leq i \leq N$，$P_i$ 是顶点 $i$ 的父节点。每个顶点都有一个美丽值，初始为 $0$。

你可以使用一台特殊机器来增加顶点的美丽值。向机器提供三个参数 $X$、$Y$ 和 $K$，机器将增加顶点 $X$ 的子树中所有顶点的美丽值。如果顶点 $X'$ 位于顶点 $X$ 的子树中，则其美丽值将增加 $\left\lfloor \frac{Y}{K^d} \right\rfloor$，其中 $d$ 是连接顶点 $X$ 到 $X'$ 的路径上的边数。例如，顶点 $X$ 的美丽值增加 $Y$，顶点 $X$ 的所有子节点的美丽值增加 $\left\lfloor \frac{Y}{K} \right\rfloor$，顶点 $X$ 的子节点的所有子节点的美丽值增加 $\left\lfloor \frac{Y}{K^2} \right\rfloor$，以此类推。

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

1. 使用特殊机器，向机器提供三个参数 $X$、$Y$ 和 $K$。
2. 报告顶点 $X$ 的子树中所有顶点的美丽值总和。

对于每个第二类操作，输出顶点 $X$ 的子树中所有顶点的美丽值总和。

输入格式

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

• $1\ X\ Y\ K$（$1 \leq X \leq N$；$1 \leq Y, K \leq 100\,000$）
  使用特殊机器，向机器提供三个参数 $X$、$Y$ 和 $K$。
• $2\ X$（$1 \leq X \leq N$）
  输出顶点 $X$ 的子树中所有顶点的美丽值总和。

保证至少有一个第二类操作。

输出格式

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

输入输出样例 #1

输入 #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$。