Background

Initial direction of the line is to be determined by yourself

After playing with $LCA$, Imakf found it quite boring, so he opened DL.

Imakf: Assassin's Legend is stuck at $70\%$! Suddenly, I have the idea of quitting...

Imakf remembered playing DL for a year, being stuck in the Chaos of the Garden Church, and after months of hard work, finally passing it. However, he was stuck in this Assassin's Legend, unable to help but tear up. In his tears, he suddenly noticed that his phone had turned into individual pixels! Imakf was very excited! Wouldn't this allow him to write a program to automatically clear the levels?

But soon, he fell into disappointment...

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

Problem Description

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

Imakf sometimes wants to show off his skills and sometimes wants to be lazy, so he will tell you the full layout of the map, and you need to tell him the maximum and minimum number of turns required to reach the destination.

Input Format

The first line contains two positive integers $M,N$, as described in the problem.

Lines $2$ through $M+1$ each contain $N$ characters. A # indicates an obstacle, otherwise, it is clear.

Output Format

Output two positive integers $max,min$, where $max$ represents the maximum number of turns, and $min$ represents the minimum number of turns.

If it is not possible to reach the destination, output only -1.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7 2

Sample Input #2

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

Sample Output #2

-1

Notes

Sample $1$ Explanation:

The red route represents the maximum number of turns.

The blue route represents the minimum number of turns.

Sample $2$ Explanation:

Clearly, it is not passable.

Data Range:

For all data, it is guaranteed that $10 \le M,N \le 1000$.

Thanks to @Iowa_BattleShip for pointing out data errors.

见题面 Input 部分

见题面 Output 部分