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