Trees - Recursive traversal P98436

Statement

thehtml

Write a program that reads the description of a natural binary tree and prints its postorder and inorder traversals.

The description of a tree consists of its traversal in preorder, which includes the leaves marked with a -1.

Have a look on the PDF file.

Input

Input consists of the description of a natural binary tree.

Output

Your program must print two lines, with the postorder and inorder traversals of the tree. Follow the format in the samples.

Public test cases

Input

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

Output

pos: 4 7 2 0 4 1 6 7 5 3
ino: 7 4 0 2 3 4 5 6 1 7

Information