You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小敌困之。剥，不利有攸往。

题目描述

33DAI 发现有 $n$ 只小猫在 $m\times m$ 的二维数组里，第 $i$ 只小猫在第 $x_i$ 行的第 $y_i$ 列（保证 $2\le x_i,y_i\le m-1$），可能有多只小猫在同一个位置。

已知每只小猫都只会往上下左右四个方向直线行走，不会拐弯。33DAI 可以在某些位置放稻草人来拦住小猫。稻草人必须放在 $m\times m$ 的二维数组内，且不能放在已经有小猫或稻草人的位置。请帮 33DAI 构造一个放稻草人的方案。

形式化的说，如果在

• 第 $x_i$ 行的第 $1\sim y_i-1$ 列
• 第 $x_i$ 行的第 $y_i+1\sim m$ 列
• 第 $y_i$ 列的第 $1\sim x_i-1$ 行
• 第 $y_i$ 列的第 $x_i+1\sim m$ 行

这四个区域都分别至少放了一个稻草人，就可以拦住第 $i$ 只小猫。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i$ 行为两个整数 $x_i,y_i$。

输出格式

显然不可能无解，最多 $4\times n$ 个稻草人肯定能拦住所有小猫，如果有多解，输出任意一种即可。

第一行需要输出一个 $1\sim 4\times n$ 范围内的整数 $k$，表示需要放 $k$ 个稻草人。

接下来 $k$ 行，第 $i$ 行为第 $i$ 个稻草人的位置 $u_i,v_i$，即放在第 $u_i$ 行的第 $v_i$ 列。

3 5
2 2
2 4
4 4

7
1 2
1 4
2 1
2 5
4 2
4 5
5 4

输出为一种可能的方案，下面是这个方案放稻草人的位置

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 500$，$3\le m\le 10^9$，$2\le x_i,y_i\le m-1$。

• 子任务 1（10 分）：保证 $m=3$。
• 子任务 2（20 分）：保证 $n=1$。
• 子任务 3（30 分）：保证 $1\le 4\times (m-1)\le 16$。
• 子任务 4（40 分）：没有特殊限制。