for this problem You will get 2 points for solving this problem.

You are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.

The root of the tree is labeled 1. Hence P[1] is set to 0. The parent of node T will always have a label less than T. Hence P[i] < i will always be true. All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0. You are asked to perform several operations of the following type

ADD X Y: add Y to the value at node X.

ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.

After you have performed all the given operations, you are asked to answer several queries of the following type

VAL X: print the value at node X.

VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).

Input

The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.

The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.

The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.

After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.

Output

Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.

Constraints

1 ≤ T ≤ 10 1 ≤ N ≤ 50000 1 ≤ M ≤ 50000 1 ≤ Q ≤ 50000 1 ≤ X ≤ N 1 ≤ Y ≤ 50000

The input file will be smaller than 2 MB. Sample Input

2 5 5 3 0 1 1 1 3 ADD 1 10 ADD 2 20 ADD 3 30 ADD 4 40 ADDUP 5 50 VAL 3 VALTREE 3 VALTREE 1 7 4 5 0 1 2 2 2 1 2 ADD 6 76 ADDUP 1 49 ADD 4 48 ADDUP 2 59 VALTREE 1 VALTREE 5 VAL 5 VALTREE 2 VAL 2

Sample Output

80 130 250 291 0 0 107 59

i write this code https://ideone.com/H0fZZR

but this gives me WA plz help me that where i was wrong plz ............... thanx in advance

Auto comment: topic has been updated by singh1495 (previous revision, new revision, compare).You don't clear vec.

but sir is there need of clearing the vec bcz i m storing only adjancy og node can u clear it means can u explain it with proper reason that in which case it fail

thanks alot sir i got it its such a my big mistake thanks for poinitout this...............

You should say didn't instead of don't

Even if I really should looks like this mistake doesn't hide the meaning. And I'm not sure if it's really a mistake. Can anybody (yeah, no way anybody will read a post called 'need help' from the green guy) prove it?

Here is proof:

If you say don't, that means DO NOT DO IT, which is a command to the guy not to clear the vec in the future.

If you say didn't, that means you point out what is wrong in the past, which means the guy forgot to clear the vec, thus he should clear the vec in the future.

Thus Don't and Didn't is exactly opposite.

Proof done.

I mean proof from someone who is known not only for stupid comments.

I hope you are just trolling and that's not your real intellectual level, there is nothing wrong with his comment.

please provide the full code

full code is already provided...........

how did you clear the vector could you provide the new code or the corrected one its urgent ,i have got the same question

https://ideone.com/lAXoLV updated code check this one

Hi can you please explain me the code for the same?

u can solve it using treap

can u give problem link?

sorry this code is from placement contest so its mow visible to everyone due to privacy issue

can anyone tell where is the error why output is not correct

## include

## include<bits/stdc++.h>

## include<string.h>

## include

using namespace std;

int main() { // your code goes here

for(i=n;i>0;i--) { value[i]+=arr[i]; for(j=0;j<vec[i].size();j++) { value[i] += value[vec[i][j]]; }

}

}