Mrw的工资计划

Mrw的工资计划

测试数据来自 system/1710

背景

传说中的Mrw神牛为新的Vijos管理团队设计了这么一种架构……

描述

新的Vijos管理团队的管理架构其实很简单:除了大老板Mrw之外,其他人都有且只有一个直接的上司。Mrw并且还定义了管理等级,他自己是1级,他的下属都是2级,他的下属的下属则都是3级,依次类推。

为了Vijos的平稳运行,初始所有人每个月都会有一个工资Vi。当然Mrw是老板嘛,所以他可以随意的加减某个管理等级的人的工资。为了公平,每次加减工资都能且只能对一个管理等级的所有人进行操作。

然而风云突变,Mrw有一天突然不爽了起来,于是他决定把管理等级为奇数的人称为“神牛”,管理等级为偶数的人为“菜鸟”。他有时会很想知道,对于两个人x, y,从x到他们的共同上司再到y这一条“管理链”中,“神牛”的工资与“菜鸟”的工资的差的绝对值是多少。

作为Mrw的财务官,请你应付Mrw漫无止境的修改工资和询问吧!

格式

输入格式

输入第一行是两个数N, Q(1 <= N <= 20000, 1 <= Q <= 100000),表示有N个人,Q次工资修改或询问。

接下来一行有N个数Ai(0 <= Ai <= 100000),表示第i个人初始的工资。

再接下来N行,每行有一个数Bossi,表示第i个人的上司是谁。Mrw的上司会被标记为-1。

最后是Q行,每行具有以下两种格式之一:
1、M lv t,表示将等级为lv的人的工资加上t,如果t为负数,则操作含义为将工资减去(-t)。(0 <= |t| <= 100000)
2、A x y,询问从x到他们的共同上司再到y这一条“管理链”中“神牛”的工资与“菜鸟”的工资的差的绝对值是多少。

注意:N位员工编号为从1到N。

输出格式

对于每个第二种询问,输出一行答案。

样例1

样例输入1

3 5
1 2 3
3
1
-1
M 2 1
A 1 1
M 2 -2
M 1 -3
A 3 2

样例输出1

2
2

限制

所有测试点1秒。