题目描述

以下のような、無限に広がる三角グリッドがあります。 座標がともに整数であるような点のそれぞれには、ランプがひとつ設置されています。

はじめ、$(X,\ 0)$ のランプのみが点灯しており、その他のランプはすべて消灯していました。 この状態から、すぬけ君が次の操作を $0$ 回以上行いました。

• $2$ つの整数 $x,\ y$ を選ぶ。 $3$ つのランプ $(x,\ y),\ (x,\ y+1),\ (x+1,\ y)$ の状態を切り替える (点灯していれば消灯させ、消灯していれば点灯させる)。

この操作のあと、$N$ 個のランプ $(x_1,\ y_1),\ \cdots,\ (x_N,\ y_N)$ が点灯しており、その他のランプはすべて消灯していました。 $X$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

$X$ を出力せよ。

题目大意

给你一个三角形坐标系，其中每个整点上都有一盏灯。最开始，只有 $(X,0)$ 上的灯是开着的，你将进行有限次以下操作（$0$ 次或更多）：

• 选择一个整数对 $(x,y)$，改变 $(x,y),(x,y+1),(x+1,y)$ 的开关状态。

操作完后，输入最后亮着的 $N(1 \leq N \leq 10^5)$ 盏灯的坐标 $(x_i,y_i)(10^{-17} \leq x_i,y_i \leq 10^{17})$，输出最开始的 $X$。数据保证 $X$ 唯一。

样例解释：

4
-2 1
-2 2
0 1
1 0

-1

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $-10^{17}\ \leq\ x_i,\ y_i\ \leq\ 10^{17}$
• $(x_i,\ y_i)$ は互いに異なる。
• 入力は問題文と矛盾せず、$X$ は一意に定まる。

Sample Explanation 1

行われた操作の列として考えられるものをひとつ、以下の画像に示します。