[Ynoi2077] stdmxeypz

题目描述

给你一棵边权为 $1$,且以 $1$ 为根的有根树,每个点有初始为 $0$ 的点权值,定义两个点的距离为其在树上构成的简单路径的长度,需要支持两种操作: `1 a x y z`:把 $a$ 子树中所有与 $a$ 的距离模 $x$ 等于 $y$ 的节点权值加 $z$。 `2 a`:查询 $a$ 节点的权值。

输入输出格式

输入格式


第一行两个整数 $n,m$ 表示树的节点数为 $n$,有 $m$ 次操作。 第二行 $n-1$ 个整数,第 $i$ 个数 $f_i$ 表示树上第 $i+1$ 个节点的父亲节点。 之后 $m$ 行,每行形如 `1 a x y z` 或 `2 a`,表示上述的操作。

输出格式


对于每个 $2$ 操作,输出一行一个整数表示答案。

输入输出样例

输入样例 #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

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 对于 $100\%$ 的数据,满足 $1\leq n , m\leq 3\times 10^5$,$1\leq f_i\leq i$,$1\leq a\leq n$,$1\leq x\leq n$,$0\leq y < x$,$0 \leq z < 514$。