中等规模的商人们想要在 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 10^4 = 100,000$，在每个满足 $|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$ 中的某一条上。

子任务

测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试组组成。