LJH的智慧树

Problem B: LJH的智慧树

Time Limit: 1 Sec Memory Limit: 256 MB

Description

在遥远的苏元山上，有一位学霸名叫ljh。他头上如同慢羊羊，长了一棵智慧树，树上结满了智慧之果。据说吃一个提神醒脑，两个永不疲劳，三个长生不老。。。可是智慧之果有大有小，当然也有不同的智慧值。最神奇的是，这些智慧值会发生变化。有时候ljh心情发生变化，那么相对应的某个智慧之果就会增加或减少某个值k，而如果他心情变化很剧烈的话，可能树的某一个分枝上的所有智慧之果的智慧值都会同时增加或减少某个相同的值k。学霸都是很寂寞的，在ljh遇到另一个学(mei)霸(nv)的时候就会打算送出一些智慧之果以(gou)示(da)友(mei)好(nv)。这时候他就要知道某一个智慧之果的智慧值是多少。因为眼睛看不到头顶(?)，所以他找到了你，他会告诉你每一次智慧值改变的情况让你记录，同样也会在遇到学(mei)霸(nv)的时候向你提出询问智慧值的多少。ljh既是学霸，也是土豪，如果你能为他解决这一大难题，作为回报他会给你2147483647 mod 1 美元作为回报。

Input

第一行有nm两个正整数，代表树有n个节点以及有m个操作。

第二行有a1，a2，a3...an n个数，代表节点初始的智慧值

第三行有f1，f2，f3...fn n个数，代表节点的父亲，其中根的父亲为0

   接下来m行，代表操作，格式如下：
    OPERATE1 X K (代表编号为x的智慧之果智慧值改变k)
    OPERATE2 X K (代表以编号为x的节点为根的分枝上的所有智慧之果智慧值改变k)
    QUERY X(询问编号为x的智慧之果的智慧值)

Output

对于所有QUERY询问，每一行输出一个值，为当前所询问的该智慧之果的智慧值。

Sample Input

5 5
1 2 3 4 5
0 1 1 2 3
QUERY 3
OPERATE1 3 10
OPERATE2 1 8
OPERATE1 3 -2	
QUERY 3

Sample Output

3
19

HINT

【数据范围】

对于30%的数据，nm<=1000

对于60%的数据，nm<=10000

对于100%的数据，nm<=100000
【大礼包提示(出题者是不是很好人？！)】

答案有可能大于2^31-1。