You bought two virtual reality glasses. There is only one game installed to both of them called "The Maze Runner".

Each glasses has its special feature.

The first glasses, allows you to pass through doors.
The second glasses, allows you to walk through walls.

The maze looks like a gird of size N×M. At first, you are at the top left corner of this grid. You want to reach the bottom right corner of this maze. You can move vertically or horizontally on the grid and need 1 minute to go from one cell to another. The cells with obstacles cannot be traversed, obstacles are represented in doors and walls. Each type of glasses allows passing one type of obstacle but not the other one.

How long do you need to reach the bottom right corner using the first glasses and second glasses?

Given the grid which represents the maze. Print the minimum time needed to reach the bottom right corner using the first and second glasses. If you can't reach the bottom right corner using either glasses, print -1.

Example

Let's assume N = 4 and M = 5, and the grid is as follows

. . . . .
* * . * *
. # # . #
. . . . .

If you use the first glass you can reach the bottom right corner following \( (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow(3,3) \rightarrow(4,3) \rightarrow(4,4) \rightarrow(4,5)\). ie by using 7 steps.

If you use the second glass can reach the bottom right corner following \((1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,4) \rightarrow(2,4) \rightarrow(3,4) \rightarrow(4,4) \rightarrow(4,5)\) ie by using 7 steps.

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and returns an integer array of length 2 containing minimum time required by each glasses.

N: Represents an integer denoting the number of rows in the grid.
M: Represents an integer denoting the number of columns in the grid.
maze: Represents a string array of size N , in which each string denotes each row of the maze.

Input format

The first line contains two integers, N, M denoting the number of rows and columns in the grid.
The following rows lines will have strings of the same length representing the maze. Each character in maze[i] will be either a '.' representing a clear passage or an '*' representing a wall or an '#' representing a door.

Output format

Two lines contain two integers, the first one denotes the minimum time you need to reach the bottom right corner with the first glasses, the second entity denotes the minimum time you need to reach the destination using the second glasses. If you can't reach the bottom right corner using either glasses, print -1.

Code Snippets

Code snippets are written in languages C, C++, Java, Python.

Constraints

1 ≤ N, M ≤ 500
It is guaranteed that all values of the maze consist of '.' for paths, '*' for walls, and '#' for doors.
The top left and bottom right corners of the maze will not be obstacles.