Preorder Traversal

Easyjavapythonccppjavascript

Given a binary tree in level-order form (integers and null, first token is the root), print its nodes in Root -> Left -> Right (preorder) order.

Input Format

The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null). It is blank when M is 0.

Output Format

Print the preorder traversal values separated by single spaces, or an empty line for an empty tree.

Example 1

Input

3
1 2 3

Output

1 2 3

Explanation: The root is visited first, then the left subtree, then the right.

Input (stdin)

Output

Run your code to see output here...