You are given n distinct integers. Starting from an empty binary search tree, insert them in the order given, using the standard BST rule: to insert a key x, walk down from the root, going left if x is smaller than the current node and right if x is larger, until an empty spot is reached, where a new node is created. No rebalancing is performed.
You are then given two integers lo and hi (lo ≤ hi). Trim the tree to this range using the following recursive rule, applied starting at the root: an empty (sub)tree trims to itself; if a node's value is less than lo, discard the node and its entire left subtree, and the trim result is the trim of its right subtree; if a node's value is greater than hi, discard the node and its entire right subtree, and the trim result is the trim of its left subtree; otherwise, keep the node, replacing its left child with the trim of its left subtree and its right child with the trim of its right subtree.
Report the in-order traversal (ascending order of the surviving keys) of the trimmed tree, space-separated on one line. If no keys survive, print the single word EMPTY.
Input format
Line 1: an integer n.
Line 2: n space-separated distinct integers — the keys, in insertion order.
Line 3: two space-separated integers lo hi.
Output format
Either a single line of space-separated integers (the surviving keys, ascending), or the single word EMPTY if none survive.
Constraints
- 1 ≤ n ≤ 40
- -1000 ≤ each key ≤ 1000, all keys distinct
- -2000 ≤ lo ≤ hi ≤ 2000