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

class BST:
  def __init__(self):
    self.root = None
  def insert(self,val):
    if self.root is None:
      self.root = Node(val)
    else:
      n = self.root
      start = 1
      while True:
        start *= 2
        if n.val > val:
            if n.left:
                n = n.left
            else:
                n.left = Node(val)
                return
        elif n.val < val:
            start += 1
            if n.right:
                n = n.right
            else:
                n.right = Node(val)
                return
        else:
          break
  def get_node(self,x):
      node = self.root
      position = 1
      while position != x:
          ppos = npos = x
          while npos != position:
              ppos = npos
              npos = npos // 2
          node = node.right if ppos&1 else node.left
          if node is None:
              return None
          position = ppos
      return node
  def query(self,a,b):
    if not self.root:
        yield from range(0)
    some_exist = True
    level = 0
    left_cutoff, right_cutoff = -1, -1
    while some_exist:
        some_exist = False
        position = 2 ** level
        end = position * 2
        if right_cutoff >= 0:
            end -= 2**(level - right_cutoff - 1)
        if left_cutoff >= 0:
            position += 2**(level - left_cutoff - 1)
        for node in map(self.get_node,range(position,end)):
            if node is None:
                continue
            if node.val < a:
                left_cutoff = level
            elif node.val > b:
                right_cutoff = level
            else:
                some_exist = True
                yield node.val
        level += 1

if __name__=="__main__":
    import random
    random.seed(None)
    tree = BST()
    for i in range(1000):
        tree.insert(random.randrange(0,10000))
    a,b = random.randrange(0,9999),random.randrange(0,9999)
    a,b = min(a,b),max(a,b)
    print("Querying range:",a,b)
    for i in tree.query(a,b):print(i)