题目描述

给定一个 N x M 的棋盘，其中部分格子不可进入。行从上到下编号为 0..N-1，列从左到右编号为 0..M-1，因此左上角坐标为 (0,0)。

棋盘上有一枚骑士，它最多可以进行 K 次跳跃。骑士只能停在可进入格子上，一次跳跃必须是标准国际象棋中骑士的合法走法。

你手里有一门火炮。每次可以向任意一个格子开火：

• 如果开火时骑士恰好在该格子上，则骑士被摧毁；
• 开火不会改变该格子的可达性；
• 在两次开火之间，骑士可以选择跳 0 次或 1 次；
• 你永远不知道骑士当前位置。

请输出一个最短开火序列，保证无论骑士最初在哪里、如何移动，只要它最多跳 K 次，就一定会被摧毁。

输入格式

第一行三个整数 N, M, K。

接下来 N 行，每行一个长度为 M 的字符串：

• . 表示该格可进入；
• # 表示该格不可进入。

输出格式

第一行输出一个整数，表示最少需要的开火次数。

接下来输出这么多行，每行两个非负整数，表示当前一次开火的格子坐标。

如果有多种最优方案，输出任意一种即可。

数据范围

• 1 <= N, M, K <= 100

子任务

• 20%：M = 2
• 额外 10%：所有格子都可进入
• 额外 20%：K 为偶数
• 其余测试无额外限制

评分方式

每个测试点单独计分。

样例 1

输入

3 5 1
.....
#####
.#.#.

输出

10
0 0
0 1
0 2
0 3
0 4
2 0
2 2
2 4
0 1
0 3

说明

在该样例中，骑士最多跳 1 次。前 5 发炮弹保证：若骑士起初在第一行且尚未跳到第三行，则一定会被击中。接下来的 3 发保证：若骑士在此期间跳到了第三行，或原本就在第三行且没有跳回第一行，则也会被击中。最后 2 发保证剩余情况同样被覆盖。

样例 2

输入

3 3 1
...
...
...

输出

13
0 0
1 0
2 0
2 1
2 2
1 2
0 2
0 1
1 1
2 1
2 0
1 0
0 0