AT_wtf19_c2 Triangular Lamps Hard
Description
[problemUrl]: https://atcoder.jp/contests/wtf19/tasks/wtf19_c2
**C1 との相違点を赤字で示します。**
以下のような、無限に広がる三角グリッドがあります。 座標がともに整数であるような点のそれぞれには、ランプがひとつ設置されています。
はじめ、**$ (X,\ Y) $** のランプのみが点灯しており、その他のランプはすべて消灯していました。 この状態から、すぬけ君が次の操作を $ 0 $ 回以上行いました。
- $ 2 $ つの整数 $ x,\ y $ を選ぶ。 $ 3 $ つのランプ $ (x,\ y),\ (x,\ y+1),\ (x+1,\ y) $ の状態を切り替える (点灯していれば消灯させ、消灯していれば点灯させる)。
この操作のあと、$ N $ 個のランプ $ (x_1,\ y_1),\ \cdots,\ (x_N,\ y_N) $ が点灯しており、その他のランプはすべて消灯していました。 **$ X $ と $ Y $** を求めてください。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ x_1 $ $ y_1 $ $ : $ $ x_N $ $ y_N $
Output Format
**$ X $ と $ Y $ を空白で区切って**出力せよ。
Explanation/Hint
### 制約
- **$ 1\ \leq\ N\ \leq\ 10^4 $**
- $ -10^{17}\ \leq\ x_i,\ y_i\ \leq\ 10^{17} $
- $ (x_i,\ y_i) $ は互いに異なる。
- 入力は問題文と矛盾せず、**$ X,\ Y $** は一通りに定まる。
### Sample Explanation 1
行われた操作の列として考えられるものをひとつ、以下の画像に示します。 