F. Obstacle Course
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Retired runner Usain Old decided to go through an obstacle course as his morning workout. The course consists of a sequence of $$$n$$$ columns of different integer heights. At any given time, Usain is on one of the columns and can only move to an adjacent column.

Usain is no longer young, so he doesn't want to injure his joints while going through the course. Moving from a column of height $$$h$$$ to an adjacent one is considered safe if its height is between $$$h - 3$$$ and $$$h + 2$$$, inclusive. If the height of the new column is at least $$$4$$$ lower, there is a risk of injuring his legs, and if it is at least $$$3$$$ higher, there is a risk of injuring his arms. Also note that Usain can move in both directions, left and right.

Help Usain find the longest section of the obstacle course that he can safely overcome. Specifically, find a pair of numbers $$$s, t$$$ with the maximum $$$|s - t|$$$, such that Usain can reach from the $$$s$$$-th column to the $$$t$$$-th column by making only safe moves.

Input

The first line of input contains two integers $$$m$$$ and $$$n$$$, separated by a space - the number of following lines in the input and the number of columns ($$$1 \leqslant n, m \leqslant n \cdot m \leqslant 10^6$$$).

The next $$$m$$$ lines represent the obstacle course as a matrix of size $$$m \times n$$$. Each line has a length of $$$n$$$ and consists of the characters "." and "#". The character "." means that the corresponding cell is empty, while "#" means that the cell is occupied by a column. All columns start at ground level. Thus, if there is a "#" in the $$$i$$$-th line at position $$$j$$$, there will be a "#" in the same position in all subsequent lines. The height of each column is determined by the number of "#" in the corresponding column of the matrix.

Output

Output two integers $$$s$$$ and $$$t$$$, separated by a space, indicating the boundaries of Usain's movement along the course. Note that the direction of movement matters, and the answers "s t" and "t s" are different.

Examples
Input
5 7
#......
#....#.
#...##.
##..###
#######
Output
1 7
Input
8 6
......
#...#.
#.#.#.
#.#.#.
#.#.#.
#.#.##
###.##
######
Output
1 1
Note

In the first example, the answer is "1 7" and it is the only correct one. With $$$s=2$$$, $$$t=7$$$, Usain can still reach the finish line, but it is not the pair of the farthest columns he can move between. With $$$s=7$$$, $$$t=1$$$, Usain would have to jump from the second column to the first, which is unsafe.

In the second example, there are too large height differences between all pairs of columns, so it is optimal for Usain to stay in place on any column.