Tree is described in the input. At the beginning in each node 0 is written. Then comes M queries.

There are 2 types of queries:

• 1 v x - increase the number in node v by x.
• 2 a b - write the sum of numbers on the simple path from a to b.

Input

On the first line N is written.

Then comes N-1 numbers (from 1 to N-1). ith of them is the parent of (i+1)th node.

Then enters number M.

After it comes M lines. each one describes the single query.

Output

Write the answer for each 2nd type of query.

Example

Input:
3
1
1
2
1 1 5
2 1 2

Output:
5

Edges are: 1-2, 1-3. After increasing the number of node 1 by 5, sum on the path from 1 to 2 becomes 5.

Constraints

1 <= N <= 100000

1 <= M <= 200000

1 <= a, b, v <= N

1 <= x <= 1000