Algorithms and Data Structures

Swap the Robots

You are working on a startup that tries to compete with Boston Dynamics. One of the challenges there is to have two robots swap their places on a grid without getting on top of each other.
The grid has height h and width w, where the floor is marked with dots (.) and walls are marked with hashtags (#).
The robots are allowed to move horizontally, vertically, and diagonally to their neighbor positions. Yet, they are not allowed to step on each other, or on the walls. On each step, both robots can make a move, or they can stay at their current positions. They cannot jump over each other during a move.
You are asked to find the minimum number of steps required to bring the first robot in place of the second one and the second one in place of the second.

Input

The first line of the input contains 2 integers h and w (1 ≤ h, w ≤ 50).
The next h lines contain w characters representing the grid.
The first robot is marked with the letter A and the second robot is marked with the letter B.

Output

The program should print the minimum number of steps required to swap the robots, and Impossible if it’s not possible to do so.

Examples

Input

4 4
AB.#
###.
...#
.###
Output

11
Input

2 2
AB
..
Output

2
Input

1 3
A.B
Output

Impossible
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue