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)$에 위치한 호텔에 머무릅니다.

사업가들은 가능한 한 빨리 어떤 교차점에서 만나기를 원합니다. 회의 장소가 결정되면, 모든 사람은 각자의 호텔에서 최단 경로를 선택하여 동시에 출발합니다. 잘 알려져 있듯이, 마지막 사람이나 마지막 두세 명을 기다리는 것은 어색한 일입니다. 따라서 당신은 $1$부터 $n$까지의 각 정수 $k$에 대하여, 해당 교차점에서 회의를 열었을 때 정확히 $k$명의 사업가가 가장 마지막에 도착하게 되는 교차점 $(x, y)$를 찾거나, 그러한 교차점이 존재하지 않음을 밝혀야 합니다. 즉, 마지막에 도착하는 사업가들과 정확히 같은 시간에 도착하는 사업가가 $k$명이 되기를 원합니다.

입력

첫 번째 줄에는 사업가의 수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 다음 $n$개의 줄에는 각 사업가의 호텔 위치가 주어집니다. $i$번째 줄($1 \le i \le n$)에는 $i$번째 사업가가 머무는 호텔의 좌표를 나타내는 두 정수 $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$명의 사업가가 마지막에 도착하게 되는 두 정수 $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$일 때 가장 늦게 도착하는 사업가들의 경로 예시를 보여줍니다.

Poniższy rysunek przedstawia przykładowe ścieżki najbardziej spóźnionych biznesmenów dla i = 3.

테스트 예제

테스트 0a 및 0b는 위의 예제들입니다. 그 외:

• 0c: $n = 42$, $i$번째 사업가는 $x_i = i, y_i = i + (i \pmod 3)$ 좌표의 호텔에 머무릅니다.
• 0d: $n = 10 \cdot 101^2 = 102,010$, $|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$ 형태의 네 직선 중 하나 위에 위치합니다.

서브태스크 및 채점

테스트 세트는 다음과 같은 서브태스크로 나뉩니다. 각 서브태스크의 테스트는 하나 이상의 개별 테스트 그룹으로 구성됩니다.