Comet OJ

C1180 [Contest #1]牛吃草问题

内存限制：256 MB 时间限制：2000 ms

题目描述

AA 家里养了一头老黄牛，并且在后院里种了几株草。更精确的说，若把后院视为平面坐标系，并给定两个正整数 $N, M$，那么在所有满足 $1 \le i \le N$ 和 $1 \le j \le M$ 的整数坐标位置 $(i, j)$ 都种了一株草。

现在 AA 用一条伸缩能力为 $r$ 的绳子把老黄牛绑在坐标 $(x, y)$ 的位置 ($r, x, y$ 必须是整数)。这条绳子很奇特，可以让老黄牛吃到所有坐标在 $(i, j)$ 且满足 $|x - i| + |y - j| \le r$ 的草。

另外 AA 希望老黄牛吃尽可能多的草，所以 AA 绑老黄牛的位置一定会满足 $r + 1 \le x \le N - r$ 以及 $r + 1 \le y \le M - r$。(为什么这样能使老黄牛吃尽可能多的草呢？请大家自己意会～)

老黄牛非常贪吃，会把所有能吃到的草啃食殆尽，现在给你 AA 家后院被老黄牛啃食完毕的景况，也就是每个坐标 $(i, j)$ 的草是否被吃掉。请回答 AA 所使用的绳子的伸缩能力为多少，以及老黄牛被绑的位置坐标。

有办法证明，在此叙述的限制下，可能的答案至多只有一种，且保证给定的数据答案一定存在。

输入格式

第一行有一个正整数 $T$ ($T \le 100$)，代表有几组数据。

接着每个数据的第一行有两个正整数 $N, M$ ($1 \le N, M \le 20$) 代表 AA 家后院有种草的坐标范围。接着还有 $N$ 行，每行有一个长度为 $M$ 且由 '#' 和 '.' 两种字符组成的字符串，若当中的第 $i$ 个字符串的第 $j$ 个字符为 '#'，代表坐标在 $(i, j)$ 的草没被老黄牛吃掉；相对的，若为 '.'，则代表该坐标的草被老黄牛吃掉了。

输出

对于每组数据，输出一行包含三个整数 $r, x, y$ 代表绳子的伸缩能力和老黄牛被绑的坐标位置。

样例

样例输入 1

3
5 6
###.##
##...#
#.....
##...#
###.##
4 3
###
###
##.
###
1 1
.

样例输出 1

2 3 4
0 3 3
0 1 1

提示