中等重要性的商人們想要在 Bajhattan 舉辦一場會議。Bajhattan 的地圖類似於一個無限的二維網格，其中大道對應於形式為 $x = a$ 的垂直線（$a$ 為整數），街道對應於形式為 $y = b$ 的水平線（$b$ 為整數）。每一條大道與街道相交形成一個座標為 $(a, b)$ 的交叉路口。從座標為 $(a, b)$ 的交叉路口，可以在一分鐘內移動到座標為 $(a \pm 1, b)$ 或 $(a, b \pm 1)$ 的交叉路口。

共有 $n$ 位商人，編號從 $1$ 到 $n$。會議開始前，第 $i$ 位商人（$1 \le i \le n$）住在座標為 $(x_i, y_i)$ 的飯店。

商人們希望儘快在某個交叉路口會合。一旦他們決定了會議地點，每個人都會同時從各自的飯店出發，選擇最短路徑前往該地點。眾所周知，等待最後一個人，甚至是最後兩三個人，都是一件尷尬的事。因此，請你針對 $1$ 到 $n$ 範圍內的每個整數 $k$，找出一個交叉路口 $(x, y)$，使得如果會議選在該處舉辦，恰好有 $k$ 位商人會最後抵達；若不存在這樣的交叉路口，則需說明。換句話說，我們希望恰好有 $k$ 位商人在最後抵達的那一刻出現在會議地點。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 10^6$)，代表商人的數量。 接下來的 $n$ 行描述他們的飯店位置。第 $i$ 行（$1 \le i \le n$）包含兩個整數 $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$)，描述第 $i$ 位商人所住飯店的座標。可能有多位商人住在同一家飯店。

輸出格式

你必須輸出 $n$ 行。第 $k$ 行（$1 \le k \le n$）應包含兩個整數 $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$)，表示若會議選在交叉路口 $(a_k, b_k)$ 舉辦，恰好有 $k$ 位商人會最後抵達；若不存在這樣的交叉路口，則輸出單字 NIE。若存在多個符合條件的交叉路口，輸出其中任意一個即可。

範例

輸入格式 1

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

輸出格式 1

1 0
0 -1
0 0
1 -1
NIE

說明

第一個範例的解釋：下圖展示了 $i = 3$ 時最晚抵達商人的路徑範例。

輸入格式 2

3
0 3
0 3
1 1

輸出格式 2

0 2
1 1
NIE

範例測試

測試組 0a 與 0b 為上述範例測試。此外：

• 0c: $n = 42$，第 $i$ 位商人住在座標為 $x_i = i, y_i = i + (i \pmod 3)$ 的飯店。
• 0d: $n = 10 \cdot 1012 = 102010$，在每個滿足 $|x|, |y| \le 50$ 的交叉路口 $(x, y)$ 處，恰好有十位商人入住。
• 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$ 其中之一上。

子任務

評分