Company Culture 3

Time limit2sMemory limit512 MB

Summary

Employees sit in a rooted tree. A praise of w given to employee i from a subordinate adds w to i and every ancestor up to the president; type 2 queries ask an employee's running total.

Level: Medium5 of 10
Topics: Tree, DFS, Prefix sum, Implementation
Solved: No attempts yet

Problem

Yeongseon's company praises from the top down. When a manager praises a direct subordinate, the praise cascades to every employee below that subordinate. Yeongseon, the president, decided to reverse the direction for exactly one day. When a subordinate praises a manager, that manager and every employee above, all the way up to the president, receive the same amount of praise.

Praise arrives in real time as queries of two kinds.

1 i w: employee i receives praise of amount $w$ from one direct subordinate. That $w$ is added to employee i and to every manager above employee i. ( $1 \le i \le n$ , $1 \le w \le 1000$ ) An employee with no direct subordinate never appears in this query.
2 i: print the total praise employee i has received so far. ( $1 \le i \le n$ )

Input

The first line has the number of employees $n$ and the number of queries $m$ . Employees are numbered 1 through $n$ . ( $2 \le n, m \le 100\,000$ )

The second line has the direct manager of employee 1 through employee $n$ , in order. A manager's number is always smaller than the employee's own number. Employee 1 is the president and has no manager, so -1 is given in that position.

Each of the next $m$ lines has one query.

Output

For every query of type 2, print the total praise that employee has received, one per line.

Examples7

Example 1

Input

Expected output

0
10
12

Example 2
Input
```
2 3
-1 1
1 1 1000
2 1
2 2
```
Expected output
```
1000
0
```

Example 3

Input

6 8
-1 1 1 1 1 1
2 1
1 1 7
2 1
2 4
1 1 993
2 1
2 6
2 2

Expected output

Example 4

Input

6 12
-1 1 1 2 2 3
2 1
1 2 5
2 1
2 2
2 3
1 3 7
2 1
2 3
1 1 3
2 1
2 2
2 4

Expected output

Example 5
Input
```
4 4
-1 1 2 2
2 1
2 2
2 3
2 4
```
Expected output
```
0
0
0
0
```

Example 6

Input

Expected output

Example 7

Input

15 20
-1 1 1 2 2 3 3 4 4 5 5 6 6 7 7
1 4 10
1 5 20
1 6 30
1 7 40
1 2 1
1 3 2
1 1 100
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13

Expected output