Description

因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为\(0\)。当城市𝑖被加派了\(k\)名士兵时。城市𝑖的所有子城市需要被加派\(k+1\)名士兵。这些子城市的所有子城市需要被加派\(k+2\)名士兵。以此类推。
当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能询问以城市\(i\)为根的子树中的所有城市共被加派了多少士兵。
你现在是国王的军事大臣，你能回答出国王的每个询问么？

Format

Input

第一行，包含两个整数\(N,P\)代表城市数量以及国王的命令的数量。
第二行\(N-1\)个整数，表示\(2\)−\(N\)号每个节点的父亲节点。
接下来的\(P\)行，每行代表国王的一个命令，命令分两种:
\(A\) \(X\) \(K\) 在城市\(X\)加入\(K\)个士兵
\(Q\) \(X\) 询问以城市\(X\)为根的子树中所有士兵数量的和。

Output

对于每个Q，输出答案。

Sample 1

Input

7 10
1 1 2 2 5 5
Q 1
A 2 1
Q 1
Q 2
Q 5
A 5 0
Q 5
A 3 1
Q 1
Q 2

Output

0
11
11
8
10
14
13

Limitation

1s, 512MiB for each test case.

Hint

样例解释

无。

数据规模与约定

对于50%的数据，\(1 ≤ N ≤ 1000 \quad 1≤ P ≤ 300\)。
对于100%的数据，\(1 ≤ N ≤ 50000 \quad 1≤ P ≤ 100000 \quad 1≤ X ≤ N \quad 0 ≤ K ≤ 1000\)。

Source

CSP2019模拟题六