NTSF - Not so fast

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


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 NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own problem

hide comments
2014-06-18 01:01:19 Tornike Mandzulashvili
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
2014-06-17 17:43:06 Jacob Plachta
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.
2014-06-17 11:22:27 Rajul
what is the significance of n-1 numbers ?
2014-06-16 19:54:15 Tornike Mandzulashvili
I'm sorry , I forgot :) I think its ready now :)

RE: Alright, it's visible now.

Last edit: 2014-06-17 04:37:11
2014-06-16 19:53:49 Rajul
@Jacob how to submit problem solution there is no language selector.
2014-06-16 19:53:49 Rajul
I am not able to see Language choice
2014-06-16 19:53:49 [Lakshman]
@Tornike Mandzulashvili First enable the languages I am unable to see the language choice drop down.

Last edit: 2014-06-16 16:51:48
2014-06-16 19:53:49 Tornike Mandzulashvili
problem solved , unhide it please
2014-06-16 19:53:49 Jacob Plachta
Please leave problems as Hidden until submissions are enabled.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.