题目描述

给定一个由“.”和“#”字符组成的n*m的网格，网格上存在一个完整的曼哈顿圆。网格的左上角坐标为(1,1) ，右下角坐标为(n,m) 。 如果|h-a| +|k-b|<r，则点（a,b）属于以（h,k）为中心的曼哈顿圆，其中r是正常数。 在网格上，作为曼哈顿圆一部分的点集被标记为“#”。找到圆心的坐标。

输入格式

第一行包含t（1<=t<=1000 ）——测试用例的数量。 每个测试用例的第一行分别包含n和m（1<=n·m<=2·100000 ）--网格的高度和宽度。 接下来的n行包含m个字符 '.' 或 '#'，如果字符是“#”，则该点是曼哈顿圆的一部分。 保证所有测试用例的n·m总和不超过2·100000 ，并且网格上有一个完整的曼哈顿圆圈。

输出格式

对于每个测试用例，输出两个整数，即圆心的坐标。

样例

6
5 5
.....
.....
..#..
.....
.....
5 5
..#..
.###.
#####
.###.
..#..
5 6
......
......
.#....
###...
.#....
1 1
#
5 6
...#..
..###.
.#####
..###.
...#..
2 10
..........
...#......

3 3
3 3
4 2
1 1
3 4
2 4

来源

Codeforces 1985D，英文题名 Manhattan Circle。