Andy 是南京大学一位首屈一指的数据结构专家。有一天，他向朋友们抛出了一个枯燥乏味的数据结构问题，但没有人能解决。你呢？

给定一棵以节点 1 为根的树。每个节点的初始权值均为 0。定义两节点之间的距离为它们之间唯一简单路径上的边数。你需要执行以下两种操作：

• 类型 1：给定 $a, x, y, z$，将所有满足“与 $a$ 的距离模 $x$ 等于 $y$”的 $a$ 的后代节点（包括 $a$ 本身）的权值增加 $z$。
• 类型 2：给定 $a$，返回节点 $a$ 的权值。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 4$)，表示测试用例的数量。

每个测试用例以两个整数 $n, m$ ($1 \le n, m \le 300000$) 开头，表示树中有 $n$ 个节点（编号为 1 到 $n$），你需要执行 $m$ 次操作。下一行包含 $n - 1$ 个整数 $f_1, f_2, \dots, f_{n-1}$ ($1 \le f_i \le i$)，用于指定树的边；第 $i$ 个整数表示节点 $i + 1$ 的父节点。接下来的 $m$ 行描述操作。每行要么是 1 a x y z ($1 \le a \le n, 1 \le x \le n, 0 \le y < x, 0 \le z \le 500$)，表示类型 1 操作；要么是 2 a ($1 \le a \le n$)，表示类型 2 操作。

输出格式

对于每个测试用例中的每个类型 2 操作，在一行中输出答案。

样例

输入 1

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

输出 1

5
0