output_description: For each query, report IDs of points such that sxi ≤ x ≤ txi and syi ≤ y ≤
  tyi. The IDs should be reported in ascending order. Print an ID in a line, and
  print a blank line at the end of output for the each query.
input_description: n
      x0 y0
      x1 y1
      :
      xn-1 yn-1
      q
      sx0 tx0 sy0 ty0
      sx1 tx1 sy1 ty1
      :
      sxq-1 txq-1 syq-1 tyq-1
      
  
  The first integer n is the number of points. In the following n lines, the
  coordinate of the i-th point is given by two integers xi and yi.
  
  The next integer q is the number of queries. In the following q lines, each
  query is given by four integers, sxi, txi, syi, tyi.
attempt: class Node:
      def __init__(self, nid, data):
          self.nid = nid
          self.data = data
          self.left = None
          self.right = None
  
  
  class KDTree:
      def __init__(self):
          self.root = None
  
      def fit(self, data):
          if len(data) == 0:
              raise Exception("List length must be larger than 0.")
          self.d = len(data[0]["value"])
          self.root = self._construct(data, 0)
  
      def _construct(self, data, depth):
          if len(data) == 0:
              return None
          elif len(data) == 1:
              return Node(data[0]["id"], data[0]["value"])
          data.sort(key=lambda x: x["value"][depth % self.d])
          mid = len(data) // 2
          node = Node(data[mid]["id"], data[mid]["value"])
          node.left = self._construct(data[:mid], depth + 1)
          node.right = self._construct(data[mid + 1 :], depth + 1)
          return node
  
      def find(self, rec):
          if self.root is None:
              raise Exception("Not yet constructed")
          if len(rec) != self.d:
              raise Exception("The number of dimensions doesn't match")
          return self._search(self.root, rec, 0)
  
      def _search(self, node, rec, depth):
          ret = []
          if node is not None:
              r = depth % self.d
              if rec[r][0] <= node.data[r]:
                  ret += self._search(node.left, rec, depth + 1)
              if node.data[r] <= rec[r][1]:
                  ret += self._search(node.right, rec, depth + 1)
              if self._contains(node, rec):
                  ret.append(node)
          return ret
  
      def _contains(self, node, rec):
          for i in range(self.d):
              if rec[i][1] < node.data[i]:
                  return False
              if node.data[i] < rec[i][0]:
                  return False
          return True
  
  
  n = int(input())
  data = []
  for i in range(n):
      x, y = list(map(int, input().split(" ")))
      data.append({"id": i, "value": (x, y)})
  
  q = int(input())
  recs = []
  for _ in range(q):
      sx, tx, sy, ty = list(map(int, input().split(" ")))
      recs.append(((sx, tx), (sy, ty)))
  
  
  tree = KDTree()
  tree.fit(data)
  
  for i in range(q):
      ret = tree.find(recs[i])
      for node in ret:
          print(node.nid)
      print()
  
problem_description: Range Search (kD Tree)
  
  The range search problem consists of a set of attributed records S to
  determine which records from S intersect with a given range.
  
  For n points on a plane, report a set of points which are within in a given
  range. Note that you do not need to consider insert and delete operations for
  the set.
samples: [{"input": "6\n    2 1\n    2 2\n    4 2\n    6 2\n    3 3\n    5 4\n    2\n    2 4 0 4\n    4 10 2 5", "output": "0\n    1\n    2\n    4\n    \n    2\n    3\n    5"}]