NTSF - Not so fast

no tags 

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

hide comments
Tornike Mandzulashvili: 2014-06-18 01:01:19

My two different solutions checked these tests and another student also solved it , I think tests are OK.

RE: Okay, that's fine.

Last edit: 2014-06-18 07:29:07
Jacob Plachta: 2014-06-17 17:43:06

This problem actually happens to be basically identical to another problem already on SPOJ (http://www.spoj.com/problems/GRAFFTOL), so it needs to be moved to Tutorial so that people don't get to solve two problems with the same solution.

However, I also get WA here with my code from that problem, which is weird - maybe the data should be checked.

Rajul: 2014-06-17 11:22:27

what is the significance of n-1 numbers ?

Tornike Mandzulashvili: 2014-06-16 19:54:15

I'm sorry , I forgot :) I think its ready now :)

RE: Alright, it's visible now.

Last edit: 2014-06-17 04:37:11
Rajul: 2014-06-16 19:53:49

@Jacob how to submit problem solution there is no language selector.

Rajul: 2014-06-16 19:53:49

I am not able to see Language choice

[Lakshman]: 2014-06-16 19:53:49

@Tornike Mandzulashvili First enable the languages I am unable to see the language choice drop down.

Last edit: 2014-06-16 16:51:48
Tornike Mandzulashvili: 2014-06-16 19:53:49

problem solved , unhide it please

Jacob Plachta: 2014-06-16 19:53:49

Please leave problems as Hidden until submissions are enabled.


Added by:Tornike Mandzulashvili
Date:2014-06-16
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem