Medium-importance businessmen want to organize a meeting in Bajhattan. The map of Bajhattan resembles an infinite two-dimensional grid, where avenues correspond to vertical lines of the form $x = a$ for integers $a$, and streets correspond to horizontal lines of the form $y = b$ for integers $b$. Each such avenue and street meet to form an intersection with coordinates $(a, b)$. From an intersection with coordinates $(a, b)$, one can move to an intersection with coordinates $(a \pm 1, b)$ or $(a, b \pm 1)$ in exactly one minute.

There are $n$ businessmen, numbered from $1$ to $n$. Before the meeting, the $i$-th businessman (for $1 \le i \le n$) stays at a hotel located at the intersection with coordinates $(x_i, y_i)$.

The businessmen want to meet at some intersection as soon as possible. As soon as they decide on the meeting place, everyone simultaneously begins their journey to it from their hotels, choosing the shortest possible path. As is well known, it is awkward to wait for the last person, or even for the last two or three. That is why you have been asked to determine, for each integer $k$ in the range from $1$ to $n$, an intersection $(x, y)$ such that if the meeting is organized at this intersection, exactly $k$ businessmen will arrive at the meeting last, or to state that no such intersection exists. In other words, we want exactly $k$ businessmen to appear at the meeting at the same moment as the last ones.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 10^6$) denoting the number of businessmen. The next $n$ lines describe their hotel locations. The $i$-th line (for $1 \le i \le n$) contains two integers $x_i, y_i$ ($-10^9 \le x_i, y_i \le 10^9$) describing the coordinates of the hotel where the $i$-th businessman is staying. It may happen that more than one businessman stays at the same hotel.

Output

You must output $n$ lines. The $k$-th line (for $1 \le k \le n$) should contain two integers $a_k, b_k$ ($-10^{18} \le a_k, b_k \le 10^{18}$) indicating that if the meeting is organized at the intersection $(a_k, b_k)$, exactly $k$ businessmen will arrive there last, or the single word NIE if no such intersection exists. If there are multiple such intersections, you may output any one of them.

Examples

Input 1

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

Output 1

1 0
0 -1
0 0
1 -1
NIE

Note

Explanation for the first example: The drawing below shows sample paths for the most delayed businessmen for $i = 3$.

Input 2

3
0 3
0 3
1 1

Output 2

0 2
1 1
NIE

Additional Test Cases

Sample tests: Tests 0a and 0b are the tests from the examples above. Additionally:

0c: $n = 42$, the $i$-th businessman stays at a hotel with coordinates $x_i = i, y_i = i + (i \pmod 3)$.

0d: $n = 10 \cdot 10^4 = 100\,000$, at every intersection $(x, y)$ such that $|x|, |y| \le 50$ there are exactly ten businessmen.

0e: $n = 3$, hotels are located at $(10^9, 10^9), (-10^9, 10^9), (-10^9, -10^9)$.

0f: $n = 4 \cdot 10^4$, the $i$-th businessman stays at a hotel with coordinates $x_i = i \cdot 10^4, y_i = i \cdot (-1)^i \cdot 10^4$.

0g: $n = 10^6$, every hotel lies on one of the four lines with the equation $y = \pm x \pm 10^9$.

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.