#A1331. [ABC305C] 饼干收集者(Snuke the Cookie Picker)

[ABC305C] 饼干收集者(Snuke the Cookie Picker)

题目描述

有一个 HHWW 列的网格。用 (i,j)(i,j) 表示从上往下第 ii 行、从左往右第 jj 列的方格。

最初,在一个至少 2×22×2 大小的矩形区域内的每个方格上都放有一块饼干,其他方格上没有饼干。

形式化地说,存在唯一一组满足以下所有条件的四个整数 (a,b,c,d) (a,b,c,d)

  1. 1  a < b  H 1\ \leq\ a\ \lt\ b\ \leq\ H
  2. 1  c < d  W 1\ \leq\ c\ \lt\ d\ \leq\ W
  3. 对于所有满足 a  i  b, c  j  d a\ \leq\ i\ \leq\ b,\ c\ \leq\ j\ \leq\ d 的方格 (i, j) (i,\ j) ,上面有一块饼干,其他方格上没有饼干。

然而,Snuke 拿走并吃掉了网格上的一块饼干。 那个含有被吃掉饼干的方格现在变成空的了。

输入给出的是 Snuke 吃掉饼干后网格的状态。 方格(i, j) (i,\ j) 的状态用字符 Si,j S_{i,j} 表示,其中 '#' 表示有饼干的方格,'.' 表示没有饼干的方格。

找出 Snuke 吃掉的饼干原本所在的方格。(答案是唯一确定的)

输入格式

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

H H W W

S1,1 S_{1,1} S1,2 S_{1,2} \dots S1,W S_{1,W}

S2,1 S_{2,1} S2,2 S_{2,2} \dots S2,W S_{2,W}

\vdots

SH,1 S_{H,1} SH,2 S_{H,2} \dots SH,W S_{H,W}

输出格式

(i, j) (i,\ j) Snuke 吃掉饼干的格子。按此顺序输出 iijj,用空格分隔。

样例 #1

样例输入 #1

5 6
......
..#.#.
..###.
..###.
......

样例输出 #1

2 4

样例 #2

样例输入 #2

3 2
#.
##
##

样例输出 #2

1 2

样例 #3

样例输入 #3

6 6
..####
..##.#
..####
..####
..####
......

样例输出 #3

2 5

提示

样例说明 1

最初,饼干放在以 (2,3)(2,3) 为左上角、(4,5)(4,5) 为右下角的矩形内的格子上,Snuke吃掉了 (2,4)(2,4) 上的饼干。因此,你应该输出 (2,4)(2,4)

样例说明 2

最初,饼干放在以 (1,1)(1,1) 为左上角、(3,2)(3,2) 为右下角的矩形内的格子上,Snuke吃掉了 (1,2)(1,2) 上的饼干。

数据范围

  • 2  H, W  500 2\ \leq\ H,\ W\ \leq\ 500
  • Si,j S_{i,j} #.