六边形图案

时间限制： 3 秒
内存限制： 512 MB
输入： 标准输入
输出： 标准输出

凯文（小黄人之一）迷上了在六边形网格上画画。六边形网格是一种将平面划分为相等正六边形的网格。每个六边形唯一对应一对整数坐标，其中第一坐标轴严格向下，第二坐标轴与它成 $120^\circ$ 角。描绘网格和坐标系的图如下所示：

当然，网格向各个方向无限延伸，但为了方便只画出了一部分。每个格子内部写有其坐标。对于格子 $(1,2)$，箭头显示了如何在坐标轴上找到它的坐标。

两个格子如果边界有公共边，则称为相邻。例如，格子 $(1,3)$ 和 $(2,2)$ 是相邻的，而 $(1,3)$ 和 $(3,2)$ 则不是。格子集合称为连通的，如果从该集合中的任意一个格子出发，每次移动到集合中与之相邻的格子，可以到达集合中的任何其他格子；称为双连通的，如果任意两个格子之间至少存在两条不相交的路径（路径上的格子互不相同）。

今天斯图尔特和鲍勃在网格上涂了一些（不一定连通的）格子，共 $n$ 个，并给凯文看。这位新手画家认为如果一个集合中没有三个两两相邻的格子（边界有公共点），则称该集合为美丽的。我们将这样的三个格子称为三角聚集。

现在凯文想知道应该擦去哪些格子，使得图中不再有三角聚集。当然，他不会向格鲁炫耀不漂亮的图案，但为了不破坏斯图尔特和鲍勃的初衷，他想尽可能少地擦掉他们涂的格子。

请帮助他解决这个问题；你不需要找到需要删除的最少格子数，但你的答案删除的格子越少，获得的分数就越高。

输入数据

第一行包含三个整数 $n$、$cost$ 和 $\gamma$，分别表示凯文得到的图中被涂格子的数量（$1 \le n \le 10^5$）、该测试的分数以及允许的精度下限（参见“评分系统”部分）。参数 $cost$ 和 $\gamma$ 用于评测你的答案，你的方案可以不使用它们。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个格子的坐标（$|x_i|, |y_i| \le 10^9$）。保证所有 $(x_i, y_i)$ 互不相同，即没有格子被重复列出。

输出数据

第一行输出一个整数 $k$ —— 你要删除的格子数。接下来 $k$ 行，每行按输入相同的格式输出被删除格子的坐标。

如果你输出了一个不属于原始集合的格子，或者删除所有列出的格子后集合中仍然存在三角聚集，你的解答将获得 WA 的评测结果。

评分系统

本题共有 43 个测试（不包括样例）。每个测试独立评分。如果你的答案在某个测试上正确，你将获得该测试的分数，公式为： $$ \text{score} = \begin{cases} 0 & \text{如果 } \frac{j}{p} < \gamma \\ \text{cost} \cdot \min\left(1, \frac{j}{p}\right) & \text{否则} \end{cases} $$ 其中 $cost$ 是测试分数，$p$ 是你的答案中删除的格子数，$j$ 是官方答案中删除的格子数，$\gamma$ 是“答案最优性”的下界。

换言之，如果你的答案比官方答案差超过 $\gamma^{-1}$ 倍，则在此测试上得 0 分。否则，你将获得该测试满分的一部分，反映出你的答案相对于官方答案的最优程度。

示例

输入

3 0 0.0
1 0
0 1
1 1

输出

1
1 0

输入

7 0 0.0
1 2
0 2
1 1
2 1
2 2
1 3
0 3

输出

1
1 2

输入

12 0 0.0
1 0
3 -1
0 1
2 0
1 1
-1 3
1 2
3 1
2 2
1 3
4 2
3 3

输出

2
1 1
1 3

备注

下面的图中画出了第三个样例的集合，并标出了所有三角聚集以及应该删除的格子。

所有格子用紫色标出。红色圆圈对应三角聚集。第一个由格子 $(0,1)$、$(1,0)$ 和 $(1,1)$ 组成；第二个由 $(1,0)$、$(1,1)$ 和 $(2,0)$ 组成；第三个由 $(1,2)$、$(1,3)$ 和 $(2,2)$ 组成。

显然，删除一个格子无法消除所有三角聚集。如果删除两个，例如 $(1,1)$ 和 $(1,3)$，则不再有三角聚集。