Right View of Binary Tree

Problem statement

A stage designer looks at a binary arrangement of lamps from its right-hand side. At each depth, only the rightmost existing lamp is visible, even when it belongs to a branch on the left side higher in the tree. Your task Return the value of the rightmost node at every level, from root level downward. Important details Do not simply follow right-child pointers: if a deeper level exists only in a left subtree, its rightmost node is still visible. Empty levels are not possible between nonempty levels. The empty tree has an empty view. Worked example For root 1, children 2 and 3, and a child 4 below node 2, the right view is 1 3 4. Node 4 is visible at the deepest level despite belonging to the left subtree.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

4
1 1 2
2 -1 3
3 -1 -1
4 -1 -1

Sample output

1 3 4