PSN0 y PSN36 están en un laberinto de tamaño ~n\times m~. Todo cuadrado del laberinto está o vacío o es una pared. Es posible moverse en el laberinto desde un cuadrado hasta cuadrados adyacentes vertical y horizontalmente. Dos personas no pueden estar en el mismo cuadrado al mismo tiempo. Nunca se puede estar en un cuadrado con una pared.

La distancia de Manhattan entre los cuadrados ~(y_1, x_1)~ y ~(y_2, x_2)~ es ~|y_1 - y_2| + |x_1 - x_2|~.

Siguiendo las reglas anteriores, ¿cuál es la mínima distancia de Manhattan que PSN0 y PSN36 pueden estar entre sí después de moverse arbitrariamente?

Subtareas

• Subtarea 1 (28 puntos): ~3 \le n,m \le 20~.
• Subtarea 2 (72 puntos): ~3 \le n,m \le 1000~.

Entrada

La primera línea contiene dos números enteros ~n~ y ~m~: las dimensiones del laberinto.

Le sigue la descripción del laberinto. Cada una de las siguientes ~n~ líneas contiene una cadena de longitud ~m~. Cada cuadrado es uno de . (vacío), # (pared), A (ubicación inicial de PSN0) y B (ubicación inicial de PSN36).

Se garantiza que cada cuadrado en el límite del laberinto sea una pared y que los caracteres ~A~ y ~B~ aparezcan exactamente una vez en la entrada.

Salida

Imprime un número entero: la distancia mínima posible.

Ejemplos

Entrada 1

5 8
########
#A#.#.B#
#.#.####
#...#..#
########

Salida 1

2

Entrada 2

5 8
########
#A#...B#
#.#.####
#...#..#
########

Salida 2

1