output_description: If the product is positive, print `Positive`. If it is negative, print
  `Negative`. If it is zero, print `Zero`.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      a b
attempt: import sys
  
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  # 「番号 n以下 の辺だけを貼ったときの連結成分の大きさが z 以上」を満たす最小のn
  # 並列二分探索
  
  N, M = map(int, readline().split())
  
  
  def find_root(root, x):
      y = root[x]
      if x == y:
          return
      find_root(root, y)
      root[x] = root[y]
  
  
  def merge(root, size, x, y):
      find_root(root, x)
      find_root(root, y)
      rx = root[x]
      ry = root[y]
      if rx == ry:
          return 0, 0
      return (ry, rx) if size[rx] < size[ry] else (rx, ry)
  
  
  def test(root, size, x, y, z):
      find_root(root, x)
      find_root(root, y)
      rx = root[x]
      ry = root[y]
      if rx == ry:
          return size[rx] >= z
      else:
          return size[rx] + size[ry] >= z
  
  
  root = list(range(N + 1))
  size = [1] * (N + 1)
  merge_1 = [0] * (M + 1)
  merge_2 = [0] * (M + 1)
  
  for t in range(1, M + 1):
      a, b = map(int, readline().split())
      x, y = merge(root, size, a, b)
      if x == 0:
          continue
      merge_1[t] = x
      merge_2[t] = y
      root[y] = x
      size[x] += size[y]
  
  Q = int(readline())
  X = []
  Y = []
  Z = []
  for line in readlines():
      x, y, z = map(int, line.split())
      X.append(x)
      Y.append(y)
      Z.append(z)
  
  left = [0] * Q  # 連結成分は z 未満
  right = [M] * Q  # 連結成分は z 以上
  q = tuple([] for _ in range(M + 1))  # 調べる時刻、番号
  done = [False] * (M + 1)
  for i in range(Q):
      q[M // 2].append(i)
  rest = Q
  
  
  while rest:
      root = list(range(N + 1))
      size = [1] * (N + 1)
      for t in range(1, M + 1):
          x = merge_1[t]
          y = merge_2[t]
          if x != 0:
              root[y] = x
              size[x] += size[y]
          if done[t] or not q[t]:
              continue
          done[t] = True
          L = left[q[t][0]]
          R = right[q[t][0]]
          ML = (t + L) // 2
          MR = (t + R) // 2
          for i in q[t]:
              x = X[i]
              y = Y[i]
              z = Z[i]
              if test(root, size, x, y, z):
                  right[i] = t
                  mid = ML
              else:
                  left[i] = t
                  mid = MR
              if left[i] < mid:
                  q[mid].append(i)
              else:
                  rest -= 1
  
  for x in right:
      print(x)
  
problem_description: Statement
  
  You are given two integers a and b (a≤b). Determine if the product of the
  integers a, a+1, …, b is positive, negative or zero.
samples: [{"input": "1 3", "output": "Positive\n    \n\n1\u00d72\u00d73=6 is positive.\n\n* * *"}, {"input": "-3 -1", "output": "Negative\n    \n\n(-3)\u00d7(-2)\u00d7(-1)=-6 is negative.\n\n* * *"}, {"input": "-1 1", "output": "Zero\n    \n\n(-1)\u00d70\u00d71=0."}]