题目内容

冷链库房的地坪划成 $h$ 行 $w$ 列的格子。货架占住的格子用 # 表示，走得动的过道用 . 表示。夜班要把两根对讲桩立在两块不同的过道上，让两桩的曼哈顿距离尽量大。格子 $(r_1,c_1)$ 与 $(r_2,c_2)$ 的曼哈顿距离是 $|r_1-r_2|+|c_1-c_2|$，按坐标直接算，中间隔着货架也不改这个值。

请给出任意一对能达到最大距离的过道坐标。行号、列号都从 1 开始。保证过道至少有两格。

约束：

• 1 $\le$ $h,w$ $\le$ 200000
• 1 $\le$ $h\times w$ $\le$ 200000
• 每个格子只可能是 . 或 #
• 过道格子数不少于 2

输入描述

第一行两个整数 $h$、$w$（1 $\le$ $h,w$ $\le$ 200000），表示行数和列数。

随后 $h$ 行，每行一个长度为 $w$ 的字符串，只含 . 与 #。

输出描述

一行四个整数 $r_1$、$c_1$、$r_2$、$c_2$，表示两根对讲桩所在过道的行号和列号。

若有多种最大方案，输出任意一种即可。

样例1

输入

3 4
.#..
#..#
..#.

输出

1 1 3 4

说明

过道里 $(1,1)$ 与 $(3,4)$ 的曼哈顿距离是 $|1-3|+|1-4|=`5`$，已经是最大。$(1,4)$ 与 $(3,1)$ 距离同样是 5，输出那一组也对。

样例2

输入

1 6
.#..#.

输出

1 1 1 6

说明

只有一行。最左和最右两块过道距离为 5，这是唯一的最大取法。

样例3

输入

4 4
#...
####
####
..##

输出

1 4 4 1

说明

$(1,4)$ 与 $(4,1)$ 距离为 6。若只拿「行加列」最小和最大的两格 $(1,2)$ 与 $(4,2)$，距离只有 3，不是最大。