After having lots of fun dealing with arithmetic sequences and squares, you decided to try combining arithmetic sequences and subtrees!
You are given a tree with vertices numbered from to , rooted at vertex . Recall that a tree is a connected graph where there is exactly one path between any two vertices. It can be seen that each vertex has a unique parent for all vertices . For simplicity, we will assume that for all .
Let be the depth of vertex and . Then for all . We define the subtree of vertex to be all vertices where and is on the unique path from vertex to vertex . Each vertex has a value, initially equal to .
You are asked to perform operations on the tree, which come in two forms.
Input Format  Description 

UPDATE u a b c 
For all vertices in the subtree of with , add to the value of vertex 
QUERY u a b 
Output the sum of the values of all vertices in the subtree of with 
Constraints
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.
Subtask  Points  Additional Constraints  


None  



and for all operations  

for all operations  

None 
For all subtasks:
for all
for all operations
for all operations
Input Specification
The first line contains 2 integers, and .
The next line contains integers: , the parent of each vertex.
The next lines each contain a valid operation as described above.
Output Specification
This problem is graded with an identical
checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n
character and that there are no trailing spaces.
For each QUERY
operation, output the answer on its own line. If there are no vertices that meet the query parameters, then the answer is .
Sample Input 1
5 4
0 1 1 3
UPDATE 0 1 2 397
QUERY 0 2 2
UPDATE 3 0 3 688
QUERY 1 1 3
Sample Output 1
1588
2673
Sample Explanation 1
After the first UPDATE
, the values of the vertices are .
After the second UPDATE
, the values of the vertices are .
Sample Input 2
5 4
0 1 2 3
UPDATE 2 1 4 541
QUERY 0 1 4
UPDATE 0 1 3 134
QUERY 0 4 1
Sample Output 2
1623
0
Sample Explanation 2
After the first UPDATE
, the values of the vertices are .
After the second UPDATE
, the values of the vertices are .
Sample Input 3
5 4
0 1 1 3
UPDATE 3 0 4 544
QUERY 4 0 4
UPDATE 1 0 4 55
QUERY 0 0 4
Sample Output 3
544
764
Sample Explanation 3
After the first UPDATE
, the values of the vertices are .
After the second UPDATE
, the values of the vertices are .
Sample Input 4
5 4
0 1 1 3
UPDATE 0 1 2 667
QUERY 0 0 1
UPDATE 0 2 3 617
QUERY 0 2 3
Sample Output 4
667
6987
Sample Explanation 4
After the first UPDATE
, the values of the vertices are .
After the second UPDATE
, the values of the vertices are .
Comments