测试数据来自 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秒。