配点 : $1000$ 点

問題文

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

はじめ、$(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$ を求めてください。

制約

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

入力

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

$N$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

出力

$X$ を出力せよ。

4
-2 1
-2 2
0 1
1 0

-1

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