题目背景

小 C 喜欢序列，小 L 喜欢树。

题目描述

你有一颗 \(n\) 个节点的树，根节点是 \(1\) 。

初始每个点的点权都是 \(0\) 。

你需要维护一个数据结构维护以下操作。

\(1,v,x\) 将编号为 \(v\) 的倍数的节点权值加 \(x\) 。

\(2,v,x\) 将编号为 \(v\) 的因数的节点权值加 \(x\) 。

\(3,l,r,x\) 将标号在区间 \([l,r]\) 的节点权值加 \(x\) 。

\(4,u,v,x\) 将 \(u\) 到 \(v\) 的简单路径上节点权值加 \(x\) 。

\(5,r\) 求出 \(\sum_{i=1}^ra_i\) 。

\(6,u\) 求出 \(1\) 到 \(u\) 简单路径的权值和。

输入格式

第一行 \(n,q\) 。

接下来一行 \(n-1\) 个正整数表示 \([2,n]\) 节点的父亲。

接下来 \(q\) 行操作。

输出格式

需要查询和的操作输出答案，换行隔开。

样例 #1

样例输入 #1

10 20
1 2 3 4 5 1 6 4 9
5 4
3 4 5 7
3 6 6 1
2 1 9
2 1 3
1 25 7
5 6
2 1 9
1 50 9
2 1 5
2 1 8
2 1 4
4 2 9 10
6 1
3 6 8 6
6 3
4 7 9 9
2 1 7
3 4 5 2
6 9

样例输出 #1

0
27
38
58
139

提示

对于 \(15\%\) 的测试数据， \(n,q,v \le 10^4\) 。

对于另外 \(15\%\) 的测试数据，没有 \(3,4\) 操作。

对于另外 \(15\%\) 的测试数据，树是一条 \(1\) 到 \(n\) 的链，即 \(\forall i\in[2,n],fa[i]=i-1\) 。

对于 \(100\%\) 的测试数据， \(n,q,v\le 2 \cdot 10^5,x\le 10^7\) 。

本题有点卡空间，请注意空间常数。