Malik just spawned in the game portal where the world is represented by a $2d$ grid that has $n$ rows and $m$ columns.

Each cell in this world can be one of the following: a wall '#' that you are unable to walk through, or a free cell '.' which you can walk through, or a portal represented by '$B$' or '$O$'.

There are two types of portals in this game, orange portals, and blue portals. Malik is able to teleport between two portals as long as they don't have the same color.

Malik's goal is to use the least possible amount of steps to go from the start point which is top-left cell (1,1) to the endpoint which is the bottom right ($n$,$m$)

Keep in mind using portals to teleport is considered a step.

The first line contains two integers n, m($1 \le n, m\le 500$), where n and m are the grid's rows and columns

Each of the next n lines contains m characters that describe the maze according to the following:

1. If a character on a line equals ".", then the corresponding cell is empty.

2. if the character equals "#", then the cell is a wall.

3. If the character equals "$O$" then the cell is an Orange Portal.

4. If the character equals "$B$" then the cell is a Blue Portal.

It is guaranteed that both the starting ($1$,$1$) and ending ($n$,$m$) cells are free cells.

Output one integer which should be the minimum number of steps needed to reach the end cell or "$-1$" if it's impossible to reach it.