Company Culture 4

Yeongseon's company praises downward. When a boss praises a direct subordinate, that subordinate's own subordinates receive praise of the same size, and it keeps spreading to the bottom of the hierarchy.

Yeongseon, the president, flips the direction in which praise spreads during the workday. The starting direction is the subordinate direction.

• Subordinate direction: when an employee receives $w$ praise, that employee and every subordinate under them each receive $w$ praise.
• Boss direction: when an employee receives $w$ praise, that employee and every boss above them each receive $w$ praise.

Praise arrives in real time. There are three kinds of queries.

• 1 i w: if the current direction is the subordinate direction, employee $i$ receives $w$ praise from the direct boss. If it is the boss direction, employee $i$ receives $w$ praise from one of the direct subordinates. Either way the praise spreads in the current direction. ($1 \le i \le n$, $1 \le w \le 1\,000$)
• 2 i: print the total praise employee $i$ has received so far.
• 3: flip the direction of praise. The subordinate direction becomes the boss direction, and the boss direction becomes the subordinate direction.

Given the direct boss of every employee and the list of queries, print the answer for every query of type 2.

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 number of the direct boss of employee 1 through employee $n$, in that order. The number of a direct boss is smaller than the employee's own number, and employee 1 is the president. Employee 1 has no boss, so -1 is given instead.

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.