We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Tree manager

Tree manager

In this problem you must perform operations on a rooted tree storing integers in each node. There are several operations to handle:

  • - Changes the value stored in the current node to .
  • - Prints the values stored in the current node.
  • - Sets the current node to be the left sibling of the current node.
  • - Sets the current node to be the right sibling of the current node.
  • - Sets the current node to be the parent of the current node.
  • - Sets the current node to be the child of the current node. Children are numbered from left to right starting from .
  • - Inserts a new node with value as the left sibling of the current node.
  • - Inserts a new node with value as the right sibling of the current node.
  • - Inserts a new node as the leftmost child of the current node.
  • - Deletes the current node with the subtree rooted in it and sets the current node as a parent of just deleted node.

Knowing that the tree initially consists of the root with value , your task is to perform consecutive operations.

Check the Input Format section for a description of how each operation is given in the input, and review the Constraints section to clarify which operations are not allowed for the root node.

Input Format

The first line contains a single integer, , denoting the number of operations to perform. The subsequent lines each describe a single operation to perform. The operations are coded as follows:

Constraints

  • It is guaranteed that all operations given as input will be valid.

Invalid operations are:

  • Visiting left/right sibling when there is no such sibling.
  • Visiting the child when there are less than children.
  • Deleting the root.
  • Inserting any sibling of the root.
  • A single node will never have more than children.

Output Format

For each operation, output a single line with the value in the current node.

Sample Input

11
change 1
print
insert child 2
visit child 1
insert right 3
visit right
print
insert right 4
delete
visit child 2
print

Sample Output

1
3
4

Explanation

There are operations to handle.

At the beginning, we change the value stored in the root to and then we print it.

After that, we insert a new child of the root with value .

Then, we visit this child and insert a new node with value as its right sibling.

Next, we visit the last inserted node and print its value.

After that, we insert a new node with value as the right sibling of last inserted node.

Then, we delete the current node (the one with value ), so the current node becomes the root.

Next, we visit the second child of the root, which is the last inserted node with value (because we deleted the node with value ).

Finally, we print the value stored in the current node, which is .