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.