Challenge: Values in a Range

Lab Python Intermediate 20 points

Build a BST from the first line, then read lo hi. Print, in sorted order, all values with lo ≤ value ≤ hi (or none). Skip subtrees that can't contain answers: don't go left when the node is already smaller than lo, and don't go right when it's bigger than hi.

Input

Line 1: whole numbers to insert. Line 2: lo hi.

Output

The values, or none.

Example

Input

50 30 70 20 40 60 80
35 65

Output

40 50 60

Sample input available Sample output available

Editor

Python

Hints

Do an inorder walk, but only visit the left side if node.value > lo.

Only visit the right side if node.value < hi.

Solution explanation

Skipping useless subtrees means you only touch about height + (number of answers) nodes.

Show solution

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root


values = list(map(int, input().split()))
root = None
for v in values:
    root = insert(root, v)
lo, hi = map(int, input().split())
out = []


def walk(n):
    if n is None:
        return
    if n.value > lo:
        walk(n.left)
    if lo <= n.value <= hi:
        out.append(n.value)
    if n.value < hi:
        walk(n.right)


walk(root)
print(" ".join(map(str, out)) if out else "none")

Output

Answer