背景

其实这哪里是部门啊明明是学校……

请注意本题的内存限制。

描述

某部门有n个人，从1到n编号，他们之间有着复杂的上下级关系。
1号是这个部门的总管，也就是说他没有上司。除了他以外，每个人都有且只有一个直接的上司，i号的直接的上司的编号为〖boss〗_i。而且，不会出现某个人的若干级上司是他自己的情况。
对应地，一些人会有直接的下属，并且可能会有多个，我们称直接的下属为1级下属，而直接的下属的直接的下属为2级下属。同样地，我们可以定义一个人的k级下属。
一开始，所有人都没有不满。然而现在，由于这个部门不太和谐，一些人可能会产生不满。同时，为了自身的利益，有些人想要知道，自己的下属的不满意度之和。由于过于高级或低级的下属对自己的影响都不是很大，他这次只会关心他的某些级别的下属。

输入格式

第一行为两个整数n q，代表人数和操作数。
第二行为(n-1)个整数，分别代表2号到n号的直接的上司的编号，即第i个数表示〖boss〗_(i+1)。
接下来q行，每行有两种可能的格式：
1 x y，表示：编号为x的人产生了y点不满意度；
2 x l r，表示：求编号为x的人的l到r级下属的不满意度之和。

输出格式

一共输出q行。
如果对应的是操作1，则输出一行-1。
如果对应的是操作2，则输出询问的答案。

样例输入

6 5
1 2 2 1 4
2 2 1 2
1 6 1086
2 2 1 2
2 2 1 1
2 2 1 5

样例输出

0
-1
1086
0
1086

数据范围与约定

除样例外，n,q=40,000，1≤〖boss〗_i<i。
对于每次操作，1≤x≤n，0≤y≤〖10〗^4，1≤l≤r≤n。

设①每个人至多有1个直接的下属；②l=1,r=n；③〖boss〗_i是随机生成的。

• 测试点1满足①②，测试点2满足②③；
• 测试点3满足①，测试点4满足②，测试点5,6满足③。

样例解释

由于6号是2号的2级下属，所以在2号统计1~2级下属时包含了6号，答案为1086，然而在统计1~1级下属时不包括6号，所以答案仍为0。

来源

原创