Company Culture 2

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.

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.

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