问题文

高桥国的高桥王为了改善国内交通便利性，决定设置一些公交车站。高桥国只有东西向和南北向的两种道路。从某一标准点开始，东方距离为 $i$ 公里的位置设置了第 $i$ 条南北向道路，北方距离为 $j$ 公里的位置设置了第 $j$ 条东西向道路。我们用 $(i, j)$ 表示第 $i$ 条南北向道路和第 $j$ 条东西向道路的交叉点。由于道路是无限长的，所以任意两条相交的道路都会在某处交叉。公交车站只能设置在交叉点上，并且同一个交叉点上最多只能设置一个公交车站。

现在已经设置了 $N$ 个公交车站。然而，高桥王发现了一个重大错误。道路太窄，公交车无法转弯。换句话说，每条线路只能沿着东西或者南北的一个方向行驶。这样一来，会出现一些只能通过公交换乘才能到达的公交车站，非常不便。因此，我们需要新增一些公交车站，通过在任意 $2$ 个公交车站之间换乘公交车来实现移动。另外，只能在公交车站进行换乘。而且，为了避免换乘路线过长，我们需要设置这样的公交车站：对于任意 $2$ 个公交车站 $(a, b), (c, d)$，它们之间的总移动距离等于公交车站之间的曼哈顿距离。也就是说，对于任意 $2$ 个公交车站 $(a, b), (c, d)$，要求存在一条换乘路径，使得总移动距离为 $|a - c|+|b - d|$ 公里。

由于预算原因，最多只能设置 $10,000$ 个公交车站，也就是说，最多只能新增 $10,000 - N$ 个公交车站。在这个范围内，当满足上述条件时，请找到新增公交车站的位置。如果有多个解，则输出任意一个解即可。

输入

输入以以下格式从标准输入中给出。

$N$ $x_1$ $y_1$ $x_2$ $y_2$ : $x_N$ $y_N$

• 第 $1$ 行是一个整数 $N (2 \leq N \leq 1,000)$，表示已经设置的公交车站的数量。
• 第 $2$ 行到第 $N$ 行，分别给出了每个公交车站所在的位置的两个整数 $x_i (1 \leq x_i \leq 1,000)$ 和 $y_i (1 \leq y_i \leq 1,000)$。表示第 $i$ 个公交车站位于交叉点 $(x_i, y_i)$ 处。
• 对于 $i \neq j$，有 $(x_i, y_i) \neq (x_j, y_j)$。
• 至少存在一个解。

部分分

本问题设置了部分分。

• 当满足 $2 \leq N \leq 100$ 的所有测试用例时，得到 $10$ 分。
• 当满足 $2 \leq N \leq 1,000$ 的所有测试用例时，额外得到 $90$ 分。总计得分为 $100$ 分。

输出

请以以下格式输出新增公交车站的位置：

$M$ $x_1$ $y_1$ $x_2$ $y_2$ : $x_M$ $y_M$

• 第 $1$ 行是一个整数 $M (0 \leq M \leq 10,000 - N)$，表示要新增的公交车站的数量。
• 第 $2$ 行到第 $M$ 行，分别给出了每个新增公交车站的位置的两个整数 $x_i (1 \leq x_i \leq 1,000)$ 和 $y_i (1 \leq y_i \leq 1,000)$。表示新增的第 $i$ 个公交车站位于交叉点 $(x_i, y_i)$ 处。
• 对于任意 $i \neq j$，有 $(x_i, y_i) \neq (x_j, y_j)$。
• 新增公交车站的位置不能与已经设置的公交车站的位置重叠。
• 对于新增的公交车站和已经存在的公交车站，对于任意 $2$ 个车站之间，最短距离必须等于曼哈顿距离。

示例1

2
1 1
2 2

输出示例1

1
1 2

通过公交车站 $(1, 1)$，公交车只能到达 $(i, 1)$ 或者 $(1, j)$（$i$，$j$ 是任意整数）。同样，通过公交车站 $(2, 2)$，公交车只能到达 $(i, 2)$ 或者 $(2, j)$。新增公交车站 $(1, 2)$ 可以实现任意两个车站之间的互相出行。注意，也可以选择新增公交车站 $(2, 1)$，或者同时新增这两个车站。

示例2

4
1 1
2 2
3 4
4 3

输出示例2

4
1 2
3 2
3 3
4 4

请注意，新增的公交车站之间的最短路径也必须满足曼哈顿距离。

示例3

7
2 4
3 2
4 6
5 1
6 5
7 3
8 7

输出示例3

15
3 6
8 5
2 2
7 5
2 5
6 6
3 1
5 6
6 2
6 1
7 1
7 2
2 3
6 7
2 6