Company Culture 3

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$)

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.

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