Fruitful Tree Magic

Harry Potter has learned a new spell that can change the number of fruits on a tree. Excited about his discovery, he finds a huge fruit tree to test his magic.

The tree has \( N \) nodes numbered from \( 0 \) to \( N-1 \) with node \( 0 \) as the root. For each node \( u \) (\( u \ge 1 \)), its parent is given as \( fa[u] \) (with \( fa[u] < u \)). Initially, all nodes have 0 fruits.

Harry's imperfect magic can only add a fixed number of fruits along a path. Each magic operation is described as follows:

[ A\ u\ v\ d ]

which means that for every node on the unique simple path between node \( u \) and node \( v \), add \( d \) fruits.

To verify his spell, Harry will ask some queries. A query is described by:

[ Q\ u ]

which asks for the total number of fruits in the subtree rooted at node \( u \) (including \( u \) itself). The subtree of a node \( u \) includes all nodes that are descendants of \( u \) in the rooted tree.

inputFormat

The first line contains two integers \( N \) and \( M \), representing the number of nodes in the tree and the number of operations, respectively.

The second line contains \( N-1 \) integers: \( fa[1], fa[2], \ldots, fa[N-1] \) where \( fa[i] \) is the parent of node \( i \).

The following \( M \) lines each describe an operation. An operation is either an update operation of the form A u v d or a query operation of the form Q u.

Note: It is guaranteed that for every update operation, there is a unique simple path between the two specified nodes.

outputFormat

For each query operation Q u, output a single integer representing the total number of fruits in the subtree rooted at node \( u \). The answers for the queries should be printed in the order they appear in the input, each on its own line.

sample

5 5
0 0 1 1
A 3 2 5
Q 0
A 4 2 3
Q 1
Q 2

20
16
8

</p>