Company Culture 2

Time limit5sMemory limit512 MB

Summary

Given a tree of boss relations, apply subtree-wide praise additions in real time and answer point total queries.

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

Problem

Yeongseon Corp has a custom called praise flowing down. When a boss praises a direct subordinate, that subordinate passes the same praise on to each of their own direct subordinates. So when an employee is praised, every employee below that employee receives the same praise.

Each praise carries a number for how strong it is, and a subordinate receives that same number.

This time the praise happens in real time. There are two kinds of queries.

1 i w: employee $i$ receives praise of strength $w$ from their direct boss.
2 i: print the total praise employee $i$ has received so far.

Given the direct boss relations and the queries, answer every query of type 2.

Input

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

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

Each of the next $m$ lines has one query. A type 1 query has the form 1 i w with $2 \le i \le n$ and $1 \le w \le 1000$ . A type 2 query has the form 2 i with $1 \le i \le n$ . The president has no boss, so the president never receives praise.

Output

For each query of type 2, print on its own line the total praise that employee has received.

Examples6

Example 1

Input

Expected output

12
6

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

Example 4

Input

Expected output

Example 5

Input

Expected output

6
10
10

Example 6

Input

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

Expected output