背景

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

请注意本题的内存限制。

描述

某部门有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。

来源

原创