En el antiguo Reino de Lúmina, los caminos están llenos de ruinas, muros colapsados y pasajes estrechos.
El mensajero real, ubicado en la posición marcada como A, debe entregar un mensaje urgente al sabio del reino, cuyo taller está marcado como B.

El mapa del reino es una cuadrícula de \(n \times m\) caracteres. Cada celda puede ser:

• A — posición inicial del mensajero
• B — destino final
• . — pasadizo libre
• # — muro derrumbado que bloquea el paso

El mensajero solo puede avanzar en cuatro direcciones: arriba, abajo, izquierda y derecha.

Tu tarea es determinar la mínima cantidad de pasos que necesita para llegar desde A hasta B.
Si no existe un camino posible, informa -1.

Input

La primera línea contiene dos enteros \(n, m\) — dimensiones de la cuadrícula
(\(1 \le n, m \le 1000\), y \(1 \le n \cdot m \le 10^6\)).

Las siguientes \(n\) líneas contienen exactamente \(m\) caracteres cada una, representando el mapa del reino.

Se garantiza que el mapa contiene exactamente un A y un B.

Output

Imprime un único entero:

• La distancia mínima en número de pasos desde A hasta B, o
• -1 si es imposible llegar.

Ejemplos

Entrada

5 6
A..#..
#...#.
###...
B.###.
#.....

Salida

15

Entrada

10 10
A.........
..###.###.
.#...#....
.#.#...###
#...###...
...#......
.##...##..
...#.#....
...#.#.###
.....#...B

Salida

50