Description

A line is on a grid map. It starts at $(1, 1)$ (top-left corner) and must reach $(M, N)$. It can only move down or right, and only on integer grid points.

Sometimes Imakf wants to show off, and sometimes he wants to be lazy, so he will give you the entire map. You need to tell him the maximum and minimum number of turns needed to reach the destination.

Input Format

The first line contains two positive integers $M$ and $N$.

Lines $2 \sim M+1$ each contain $N$ characters. A # denotes an obstacle; otherwise, the cell is free.

Output Format

Output two positive integers $max$ and $min$. $max$ is the maximum number of turns, and $min$ is the minimum number of turns. If the destination is unreachable, output -1.

5 5
oooo#
ooooo
#oo#o
o#ooo
oo#oo

7 2

5 5
oooo#
ooooo
#oo##
o#o#o
oo#oo

-1

Hint

Explanation for Sample $1$:

The red route has the most turns, and the blue route has the fewest turns.

Explanation for Sample $2$:

Unreachable, so output -1.

Constraints:

For $100\%$ of the testdata, it is guaranteed that $10 \le M, N \le 1000$.

Thanks to @Iowa_BattleShip for pointing out the data error.

Translated by ChatGPT 5