A fortress wall is walked anticlockwise around the outline of a binary tree. Emit the node values in this order, listing any node at most once (keeping only its first appearance):
- the root;
- the left boundary, top to bottom: start at the root's left child and repeatedly move to the left child if it exists, otherwise the right child, but skip any node that is a leaf;
- all leaves, in left-to-right order (the order a left-before-right depth-first walk reaches them), excluding the root;
- the right boundary, bottom to top: collect nodes by starting at the root's right child and repeatedly moving to the right child if it exists, otherwise the left child, skipping leaves, then reverse that list.
If the tree is a single node, output just that node.
Input format
Line 1: an integer n, the number of tokens on the next line.
Line 2: n space-separated tokens describing a binary tree in level-order (breadth-first). The first token is the root's value. Reading left to right, keep a queue of already-created nodes; for each node taken from the front of the queue, the next two tokens are its left child then its right child, where the token null marks a missing child. Only non-null children are added to the queue. Trailing null tokens for absent children at the deepest level may be omitted. Every node value is an integer.
Output format
A single line: the boundary node values in anticlockwise order, each listed once, space-separated.
Constraints
- 1 <= n <= 129
- The tree has at least 1 and at most 40 nodes.
- Each node value is an integer with -1000 <= value <= 1000.