## Baltic OI '13 P1 - Ball Machine

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem types
##### Baltic Olympiad in Informatics: 2013 Day 1, Problem 1

We have a "ball machine" that can be visualized as a rooted tree. The nodes of the tree are numbered from to . Each node is either empty or contains one ball. Initially, all nodes are empty. While running, the machine can perform operations of two different types:

1. Add balls to the ball machine: Balls are put one by one into the root node. As long as a ball has an empty node directly beneath it, it will roll down. If there are multiple empty child nodes, the ball will choose the one which has the node with the smallest number in its subtree. So if the ball rolls down multiple levels, it makes a choice at each level. For example: If we add two balls to the machine in the picture below, they will go to nodes and : The first ball rolls from node to node because node is empty and it contains node in its subtree (which consists of nodes and ); it further rolls from node to node . The second ball rolls from node to node as well and stops there.
2. Remove a ball from a specified node: This node becomes empty and balls from above (if there are any) roll down. Whenever a parent of an empty node contains a ball, this ball will roll down. If we remove balls from nodes , and (in this order) from the machine in the picture below, nodes , and will become empty.

#### Input Specification

The first line contains two integers and – the number of tree nodes and the number of operations.

The next lines describe the ball machine. Each of these lines contains one integer, the number of a node: the -th of these lines contains the number of node 's parent node, or if node is the tree root.

Each of the next lines contains two integers and describes an operation to be performed. An operation of type is denoted by 1 k where is the number of balls to be added to the machine. An operation of type is denoted by 2 x where is the number of the node from which a ball is to be removed.

It is guaranteed that all performed operations are correct: Operations will not require to add more balls than there are empty nodes in the ball machine or to remove a ball from an empty node.

#### Output Specification

For each operation of type , output the number of the node where the last inserted ball ended up. For each operation of type output the number of balls that rolled down after removing the ball from the specified node.

#### Sample Input

8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8

#### Sample Output

1
3
2
2