This is the python starter code:

class Node(object): def __init__(self): self.guide = None # guide points to max key in subtree rooted at node class InternalNode(Node): def __init__(self): Node.__init__(self) self.child0 = None self.child1 = None self.child2 = None # child0 and child1 are always non-none # child2 is none iff node has only 2 children def tlist(self): children = self.child0.tlist() children.extend(self.child1.tlist()) if not self.child2 is None: children.extend(self.child2.tlist()) offset = [" " + i for i in children] offset.insert(1, self.guide) return offset def __str__(self): return " ".join(self.tlist()) class LeafNode(Node): def __init__(self): Node.__init__(self) self.value = None # guide points to the key def tlist(self): return [str(self.guide) + " " + str(self.value)] def __str__(self): return " ".join(self.tlist()) class TwoThreeTree: def __init__(self): self.root = None self.height = -1 class WorkSpace: def __init__(self): self.newNode = None self.offset = None self.guideChanged = None self.scratch = [None] * 4 def insert(key, value, tree): # insert a key value pair into tree (overwrite existsing value # if key is already present) h = tree.height if h == -1: newLeaf = LeafNode() newLeaf.guide = key newLeaf.value = value tree.root = newLeaf tree.height = 0 else: ws = doInsert(key, value, tree.root, h) if ws != None and ws.newNode != None: # create a new root newRoot = InternalNode() if ws.offset == 0: newRoot.child0 = ws.newNode newRoot.child1 = tree.root else: newRoot.child0 = tree.root newRoot.child1 = ws.newNode resetGuide(newRoot) tree.root = newRoot tree.height = h + 1 def doInsert(key, value, p, h): # auxiliary recursive routine for insert if h == 0: # we're at the leaf level, so compare and # either update value or insert new leaf leaf = p #downcast (unnecessary in python) cmp = 0 if key  leaf.guide: cmp = 1 if cmp == 0: leaf.value = value return None # create new leaf node and insert into tree newLeaf = LeafNode() newLeaf.guide = key newLeaf.value = value offset = 1 if cmp  newLeaf inserted as left sibling # offset == 1 => newLeaf inserted as right sibling ws = WorkSpace() ws.newNode = newLeaf ws.offset = offset ws.scratch = [None] * 4 return ws else: q = p # downcast (unnecessary in python) pos = 2 ws = None if key   While Arthur is spending time trying to get back to Earth in different dimensions, Ford has been thinking of crashing the different planets made by the Magrathean staff. Ford is too much of a frood to not have fun visiting any of them in the name of research for the guide He found you sitting in a bar drinking a pan galactic gargle blaster, blown out of your mind and talked to you about the planet database of the Magratheans. He would like to know the entrance fees of all the planets between some planet names. Help him get the information when the hangover passes. There will be a single type of query to the database  given two planet names return the list of planet names and entrance fees of all planets between the two queried names, in lexicographic order Input Format The first line contains a number n, which is the size of the database. The next n lines are of the form - the planet name, k-the entrance fee of the planet, separated by a single space. The next line contains a number m the number of queries to the database. The next m lines are of the form .ab a,b-planet names. Constraints n, m