Bajhattanの中堅ビジネスマンたちが会議を計画している。Bajhattanの地図は無限の2次元グリッドに似ており、大通りは整数 $a$ に対する垂直線 $x = a$、通りは整数 $b$ に対する水平線 $y = b$ に対応している。これらすべての大通りと通りは交差し、座標 $(a, b)$ の交差点を形成する。座標 $(a, b)$ の交差点から、座標 $(a \pm 1, b)$ または $(a, b \pm 1)$ の交差点へちょうど1分で移動できる。

$1$ から $n$ までの番号が振られた $n$ 人のビジネスマンがいる。会議の前に、$i$ 番目のビジネスマン（$1 \le i \le n$）は座標 $(x_i, y_i)$ にあるホテルに滞在している。

ビジネスマンたちはできるだけ早くある交差点で会いたいと考えている。会議場所を決定すると、全員が同時にホテルから最短経路を選んで出発する。よく知られているように、最後の人、あるいは最後から2人目や3人目を待つのは気まずいものである。そのため、各整数 $k$ ($1 \le k \le n$) に対して、その交差点で会議を開いた場合に、ちょうど $k$ 人のビジネスマンが最後に到着するような交差点 $(x, y)$ を求めるか、そのような交差点が存在しないことを示すことが求められている。言い換えれば、最後に到着するビジネスマンの人数がちょうど $k$ 人になるような場所を探したいということである。

入力

入力の最初の行には、ビジネスマンの人数を表す整数 $n$ ($1 \le n \le 10^6$) が含まれる。 続く $n$ 行は彼らのホテルの場所を表す。$i$ 番目の行（$1 \le i \le n$）には、$i$ 番目のビジネスマンが滞在しているホテルの座標を表す2つの整数 $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) が含まれる。複数のビジネスマンが同じホテルに滞在している場合もある。

出力

$n$ 行を出力しなければならない。$k$ 行目（$1 \le k \le n$）には、会議を交差点 $(a_k, b_k)$ で開催した場合に、ちょうど $k$ 人のビジネスマンが最後に到着することを示す2つの整数 $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$) を出力する。もしそのような交差点が存在しない場合は、単語 NIE を出力する。そのような交差点が複数存在する場合は、そのうちのどれを出力してもよい。

入出力例

入力 1

5
-1 0
3 0
-2 -1
1 2
1 -1

出力 1

1 0
0 -1
0 0
1 -1
NIE

入力 2

3
0 3
0 3
1 1

出力 2

0 2
1 1
NIE

注記

最初の例の説明：下の図は $i = 3$ の場合の、最も遅く到着するビジネスマンの経路例を示している。

テスト例

テスト例 0a および 0b は上記の入出力例である。これらに加えて、以下のテストケースが存在する。

• 0c: $n = 42$、$i$ 番目のビジネスマンは座標 $x_i = i, y_i = i + (i \pmod 3)$ のホテルに滞在している。
• 0d: $n = 10 \cdot 101^2 = 102010$。$|x|, |y| \le 50$ である各交差点 $(x, y)$ にちょうど10人のビジネスマンが滞在している。
• 0e: $n = 3$。ホテルは順に $(10^9, 10^9), (-10^9, 10^9), (-10^9, -10^9)$ に位置する。
• 0f: $n = 4 \cdot 10^4$。$i$ 番目のビジネスマンは座標 $x_i = i \cdot 10^4, y_i = i \cdot (-1)^i \cdot 10^4$ のホテルに滞在している。
• 0g: $n = 10^6$。すべてのホテルは $y = \pm x \pm 10^9$ のいずれかの直線上に位置する。

小課題

テストセットは以下の小課題に分けられる。各小課題のテストは1つ以上の独立したテストグループで構成される。

採点

この問題では、各テストケースに対して $n$ 行の出力が求められます。各行において、条件を満たす交差点 $(a_k, b_k)$ を正しく出力した場合にその小課題の点数が与えられます。もし条件を満たす交差点が存在しない場合に正しく NIE と出力した場合も同様です。すべての小課題において、すべての $k$ に対して正しい出力を行った場合に満点となります。