output_description: Print X.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      x_1 y_1
      :
      x_N y_N
attempt: import sys
  from collections import defaultdict
  from heapq import heapify, heappop, heappush
  
  
  def up(lights, y, l, r, ys):
      ny = y + r - l
      if l in lights[ny]:
          lights[ny].remove(l)
      else:
          lights[ny].add(l)
      heappush(ys, ny)
  
  
  def move(lights):
      new_lights = defaultdict(set)
      for y, xs in lights.items():
          for x in xs:
              new_lights[-(x + y)].add(y)
      lights = new_lights
      ys = list(lights.keys())
      heapify(ys)
      prev_y = None
      while ys:
          y = heappop(ys)
          if y == prev_y:
              continue
          xs = sorted(lights[y])
          for l, r in zip(xs[::2], xs[1::2]):
              f = l
              while f < r:
                  d = 1
                  while f + d <= r:
                      d <<= 1
                  d >>= 1
                  up(lights, y, f, f + d, ys)
                  f += d + 1
              lights[y].difference_update({l, r})
          prev_y = y
      return lights
  
  
  n = int(input())
  xys = [tuple(map(int, line.split())) for line in sys.stdin]
  lights = defaultdict(set)
  for x, y in xys:
      lights[y].add(x)
  
  lights = move(lights)
  lights = move(lights)
  lights = move(lights)
  print(lights[0].pop())
  
problem_description: Statement
  
  There is an infinitely large triangular grid, as shown below. Each point with
  integer coordinates contains a lamp.
  
  ![](https://img.atcoder.jp/wtf19/f617c94527a62ed72fe7db12b6d1f6b0.png)
  
  Initially, only the lamp at (X, 0) was on, and all other lamps were off. Then,
  Snuke performed the following operation zero or more times:
  
    * Choose two integers x and y. Toggle (on to off, off to on) the following three lamps: (x, y), (x, y+1), (x+1, y).
  
  After the operations, N lamps (x_1, y_1), \cdots, (x_N, y_N) are on, and all
  other lamps are off. Find X.
samples: [{"input": "4\n    -2 1\n    -2 2\n    0 1\n    1 0", "output": "-1\n    \n\nThe following picture shows one possible sequence of operations:\n\n![](https://img.atcoder.jp/wtf19/cff6dc4d81e995e9300ccbaca5bf85de.png)"}]