Các doanh nhân có tầm quan trọng trung bình muốn tổ chức một cuộc họp tại Bajhattan. Bản đồ của Bajhattan giống như một lưới hai chiều vô hạn, trong đó các đại lộ tương ứng với các đường thẳng đứng có dạng $x = a$ với $a$ là các số nguyên, và các con phố tương ứng với các đường nằm ngang có dạng $y = b$ với $b$ là các số nguyên. Mỗi đại lộ và con phố như vậy gặp nhau tạo thành một giao lộ có tọa độ $(a, b)$. Từ một giao lộ có tọa độ $(a, b)$, người ta có thể di chuyển đến một giao lộ có tọa độ $(a \pm 1, b)$ hoặc $(a, b \pm 1)$ trong đúng một phút.

Có $n$ doanh nhân, được đánh số từ $1$ đến $n$. Trước cuộc họp, doanh nhân thứ $i$ (với $1 \le i \le n$) ở tại một khách sạn nằm ở giao lộ có tọa độ $(x_i, y_i)$.

Các doanh nhân muốn gặp nhau tại một giao lộ nào đó càng sớm càng tốt. Ngay khi họ quyết định địa điểm họp, mọi người đồng thời bắt đầu hành trình đến đó từ khách sạn của họ, chọn con đường ngắn nhất có thể. Như đã biết, việc chờ đợi người cuối cùng, hoặc thậm chí là hai hay ba người cuối cùng, là điều rất bất tiện. Đó là lý do tại sao bạn được yêu cầu xác định, với mỗi số nguyên $k$ trong phạm vi từ $1$ đến $n$, một giao lộ $(x, y)$ sao cho nếu cuộc họp được tổ chức tại giao lộ này, thì đúng $k$ doanh nhân sẽ đến cuộc họp cuối cùng, hoặc thông báo rằng không tồn tại giao lộ như vậy. Nói cách khác, chúng ta muốn đúng $k$ doanh nhân xuất hiện tại cuộc họp cùng một lúc với những người đến cuối cùng.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 10^6$) biểu thị số lượng doanh nhân. $n$ dòng tiếp theo mô tả vị trí khách sạn của họ. Dòng thứ $i$ (với $1 \le i \le n$) chứa hai số nguyên $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) mô tả tọa độ khách sạn nơi doanh nhân thứ $i$ đang ở. Có thể xảy ra trường hợp nhiều hơn một doanh nhân ở cùng một khách sạn.

Dữ liệu ra

Bạn phải xuất ra $n$ dòng. Dòng thứ $k$ (với $1 \le k \le n$) nên chứa hai số nguyên $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$) chỉ ra rằng nếu cuộc họp được tổ chức tại giao lộ $(a_k, b_k)$, thì đúng $k$ doanh nhân sẽ đến đó cuối cùng, hoặc từ duy nhất NIE nếu không tồn tại giao lộ như vậy. Nếu có nhiều giao lộ như vậy, bạn có thể xuất ra bất kỳ giao lộ nào trong số đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1 0
0 -1
0 0
1 -1
NIE

Ghi chú

Giải thích cho ví dụ đầu tiên: Hình vẽ dưới đây cho thấy các đường đi mẫu cho những doanh nhân đến muộn nhất đối với $i = 3$.

Dữ liệu vào 2

3
0 3
0 3
1 1

Dữ liệu ra 2

0 2
1 1
NIE