Seungbeom Corporation

Seungbeom has long admired the rapper Dok2, but he realizes he cannot rap as well as Dok2, so he decides to at least earn as much money as Dok2. He takes a leave of absence from school and founds Seungbeom Corp.

Seungbeom Corp. is a multi-level marketing company made up entirely of salespeople.

Every salesperson except Seungbeom is assigned a mentor, and each member has exactly one mentor. If salesperson A is the mentor of B, then B is called a mentee of A.

Seungbeom Corp. has a peculiar profit structure.

Salespeople buy products with their own money and sell them. If a salesperson sells a product for less than its purchase price, that salesperson takes a loss, and every mentee of that member takes the same loss. Then the mentees' mentees take the same loss, and their mentees take the same loss as well, and so on; in the end, A and every salesperson below A take the same loss that A took.

Conversely, if salesperson A sells a product at a high price and makes a profit, A and every salesperson below A gain the same profit.

To monitor how much money the employees have earned so far, Seungbeom must process the following two kinds of commands.

• 1 i w : employee i makes a profit or takes a loss of w. (A profit is given as a positive number, a loss as a negative number.)
• 2 i : print employee i's current bank account balance.

The employees start work with empty bank accounts, and profits and losses are recorded in the accounts in real time. The balance may of course be negative.

Just before starting work, Seungbeom recalls that he left a Platinum promotion match waiting, so he hands the work to us and runs home.

Let us solve the problem for Seungbeom, who is forever Gold.

The first line gives the number of salespeople including Seungbeom, N (1 ≤ N ≤ 100,000), and the number of commands, M (1 ≤ M ≤ 100,000). The salespeople are numbered from 1 to N, and Seungbeom is always number 1.

The second line gives the mentors of salespeople 1 through N in order, separated by spaces. Seungbeom has no mentor, so -1 is given for him.

From the third line, M lines follow, each containing one of the commands described above (i and w are integers, 1 ≤ i ≤ N, -10,000 ≤ w ≤ 10,000).

For each command of type 2, print the balance of the corresponding employee i on its own line.