题目描述

十字绣是一种历史悠久的刺绣方式。一个十字绣图案由布料正面的若干个十字组成，这些十字在布料背面通过线段连接。传统上，整个图案应当使用一根连续的线完成。

Carol 准备批量生产十字绣套装。每套包含一块矩形布料和完成对应图案所需的线。她希望所需线的总长度尽可能短。

现在给定图案的正面。每个标记为 X 的格子都表示一个标准十字，即在该单位格的四个角之间绣出两条对角线。你需要在保证正面恰好绣出这些十字的前提下，设计针线在布料背面的连接方式，使所需线的总长度最小。

题目保证所有十字是 8-连通 的，也就是说，从任意一个十字出发，可以通过若干次国际象棋中王的移动（横、竖或斜向移动一格）到达任意其他十字。

布料左上角坐标为 $(0,0)$，右下角坐标为 $(w,h)$。

一针由针从布料的一侧穿到另一侧形成。输出的路径中：

• 第 1 针从背面穿到正面；
• 第 2 针从正面穿回背面；
• 第 3 针再次从背面穿到正面；
• 依此交替。

布料背面的针脚允许重复，但正面的针脚不允许重复。任何一针的长度都不能为 $0$。

输入格式

第一行包含两个整数 $w,h$，表示布料的宽和高：

接下来 $h$ 行，每行包含 $w$ 个字符：

• X 表示该格中有一个十字；
• . 表示空格。

图案至少包含一个十字，并保证所有十字 8-连通。

输出格式

第一行输出一个整数 $n$，表示完成整个图案所需要的针数。

接下来输出 $n+1$ 行，第 $i$ 行给出一个穿针点的坐标 $x_i,y_i$（$i=0,1,\ldots,n$）。

连续两个点 $(x_{i-1},y_{i-1})$ 与 $(x_i,y_i)$ 之间构成第 $i$ 针。

要求：

• 第 1 针位于正面，第 2 针位于背面，之后依次交替；
• 背面的针脚可以重复；
• 正面的针脚不能重复；
• 任意一针长度均不能为 $0$；
• 构造必须完成给定十字图案，并使总用线长度最小。

样例

3 2
.XX
..X

11
1 1
2 0
2 1
3 0
2 0
3 1
2 1
3 2
2 2
3 1
2 1
1 0