PDF DownLoad

本场竞赛的PDF题面：下载

Description

在一个无限大的二维平面网格上，初始时有 $n$ 个黑子，其余均为白子。小 B 每次可以选择棋盘上的一个 $2 \times 2$ 的区域，并执行以下两种操作之一（将区域内的黑点变白，白点变黑）：

• 操作 1：反转右上角、左下角、右下角的三个点。
• 操作 2：反转左上角、左下角、右下角的三个点。

小 A 的目标是通过若干次操作，使得棋盘上剩余的黑子数量最少。如果在黑子数量最少的情况下有多种方案，他希望剩下的黑子到原点 $(0,0)$ 的欧几里得距离（直线距离）之和最小。

请你编写一个程序，输出最终剩余的最少黑子数量，以及这些黑子的坐标。

欧几里得距离：对于二维平面上的任意两点 $(x_1, y_1)$ 和 $(x_2, y_2)$，它们的欧几里得距离等于横坐标差值与纵坐标差值平方和的算术平方根：

Format

Input

第一行包含一个整数 $n(1\le n\le 10^5)$，表示初始黑点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i, y_i(|x_i|,|y_i| \le 10^9)$，表示第 $i$ 个初始黑子的坐标。保证初始给定的点互不相同。

Output

第一行输出一个整数 $m$，表示能够达到的最少黑点数量。

接下来 $m$ 行，每行输出两个整数，表示最终剩下的黑点坐标（按照到原点 $(0,0)$ 的欧几里得距离从小到大排序，若距离相同则按 $x$ 坐标升序，再按 $y$ 坐标升序）。

Samples

4
0 0
0 1
1 1
2 0

0