Ball Machine

Time limit1sMemory limit128 MB

Summary

Simulate a ball machine on a rooted tree: dropping balls follows a fixed priority path, and removing a ball makes balls above roll down; report resting node or number of moves.

Level: Hard8 of 10
Topics: Tree, Simulation, DFS, Implementation
Solved: No attempts yet

Problem

A ball machine is a rooted tree whose $N$ nodes are numbered from $1$ to $N$ . Each node is either empty or holds a single ball. Initially every node is empty. The machine supports two kinds of operations.

Operation 1 — add $k$ balls. The balls are dropped into the root one at a time. A ball keeps rolling downward as long as the node it currently sits on has at least one empty child. When several children are empty, the ball rolls into the child whose subtree contains the smallest node number. The ball stops as soon as it reaches a node that has no empty child.

For example, dropping two balls into the machine shown below sends them to nodes 1 and 3. The first ball rolls from node 4 to node 3, because node 3 is empty and its subtree (consisting of nodes 3 and 1) contains node 1; it then rolls on from node 3 to node 1. The second ball also rolls from node 4 to node 3 and stops there.

Operation 2 — remove the ball at a given node. The chosen node becomes empty, after which the balls above it settle down: whenever the parent of an empty node holds a ball, that ball rolls down into it.

For example, removing the balls at nodes 5, 7 and 8 (in this order) from the machine shown below leaves nodes 1, 2 and 3 empty.

Input

The first line contains two integers $N$ and $Q$ — the number of nodes and the number of operations. Of the next $N$ lines, the $i$ -th contains one integer: the parent of node $i$ , or $0$ if node $i$ is the root. Each of the following $Q$ lines describes one operation: 1 k adds $k$ balls, and 2 x removes the ball at node $x$ .

Every operation is guaranteed to be valid: an add never inserts more balls than there are empty nodes, and a remove never targets an empty node.

Output

Print one integer per line, in the order the operations are given.

For an operation of type 1, print the number of the node where the last of the inserted balls came to rest.
For an operation of type 2, print how many balls rolled down after the removal.

Constraints

$1 \le N \le 100000$
$1 \le Q \le 100000$
The input always describes a single tree with exactly one root (whose parent is $0$ ).

Examples2

Example 1

Input

Expected output

Example 2
Input
```
1 2
0
1 1
2 1
```
Expected output
```
1
0
```