B - 同一円周上 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

座標平面上に N 個の点があります。

これらの点は全て、x 座標 と y 座標の値が共に整数です。つまり格子点上にあります。

そのうえ、これらの点は全て、ある点 P とのマンハッタン距離が同じであることがわかっています。ここで、マンハッタン距離とは、 2 つの点の座標がそれぞれ (a, b), (c, d) であるとき、 | a-c | + | b-d | で計算される距離のことです。

そして、点 P も格子点上にあります。

点 P としてあり得る点を 1 つ挙げてください。

入力

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

N
x_1 y_1
x_2 y_2
:
x_N y_N
  • 1 行目には点の個数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の点の座標を表す 2 つの整数 x_i, y_i(-10^9 ≦ x_i, y_i ≦ 10^9)が与えられる。
  • i ≠ j ならば (x_i, y_i) ≠ (x_j, y_j) が成り立つ。
  • N 個の点は必ずある点からのマンハッタン距離が等しい。

出力

点 P としてあり得る点の x 座標の値 Pxと y 座標の値 Py を順に空白区切りで1行に出力せよ。

このとき -10^9 ≦ Px, Py ≦ 10^9 が成り立ってなければならない(そのような解が存在することは保証される)。

出力の末尾に改行を入れること。

入力例1

3
1 2
3 4
2 5

出力例1

2 3

与えられた点は全て点 (2, 3) からのマンハッタン距離が 2 です。

入力例2

3
0 1
1 0
-1 0

出力例2

0 -2016

y ≦ 0 であるような点 (0, y) は全て、点 P としての条件を満たします。 この場合 -10^9 ≦ y であるかぎり、どれを出力しても構いません。