Background

The initial facing direction of the line can be chosen by yourself.

After playing with LCA, Imakf felt bored and opened DL.

Imakf: Assassin Legend died again at $70\%$! I suddenly feel like quitting...

Imakf remembered that after playing DL for $1$ year, getting stuck on "Garden", "Church", and "Chaos", he finally cleared them after months of grinding and was delighted, but now he is trapped by this Assassin Legend again, and tears welled up in his eyes. Through the tears, he suddenly saw the phone turn into pixels! Imakf was thrilled! Then he could write a program to clear it automatically, right?

But shortly after, disappointment returned...

Imakf: I don’t know how to write it!!

Problem 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