TaK Code

题目描述

高桥君发明了一种名为 TaK Code 的二维条码。TaK Code 满足以下全部条件:

• 是由 9 行 9 列组成的区域。
• 左上角和右下角的两个 $3\times 3$ 区域中的全部 $18$ 个格子均为黑色。
• 与左上角或右下角的 $3\times 3$ 区域相邻(水平、垂直或对角相邻)的全部 $14$ 个格子均为白色。
• TaK Code 不允许旋转。

现给定一个 $N$ 行 $M$ 列的网格。网格的状态由 $N$ 个长度为 $M$ 的字符串 $S_1,\ldots,S_N$ 描述。第 $i$ 行第 $j$ 列的格子,当 $S_i$ 的第 $j$ 个字符为 # 时为黑色,为 . 时为白色。

请找出所有完全包含在该网格内、满足 TaK Code 条件的 $9\times 9$ 区域。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$S_1$
$\vdots$
$S_N$

输出格式

对于所有满足「左上角位于第 $i$ 行第 $j$ 列的 $9\times 9$ 区域满足 TaK Code 条件」的数对 $(i,j)$,输出一行,按 $i$、空格、$j$ 的顺序给出。

数对必须按字典序升序排列;即 $i$ 按升序排列,在同一 $i$ 内 $j$ 按升序排列。

样例

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

1 1
1 10
7 7
10 2

TaK Code 的形状如下所示,其中 # 为黑色格子,. 为白色格子,? 既可以为黑色也可以为白色。

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

在输入给出的网格中,左上角位于第 $10$ 行第 $2$ 列的 $9\times 9$ 区域满足 TaK Code 条件,如下所示:

###......
###......
###......
.........
..##.....
..##.....
......###
......###
......###

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

1 1

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

也可能不存在满足 TaK Code 条件的区域。

数据范围

• $9 \le N,M \le 100$
• $N$ 和 $M$ 是整数。
• $S_i$ 是由 . 和 # 组成的长度为 $M$ 的字符串。