Knowing that lich Sandro left to fight the King of Hell, Erathian commanders decided to take advantage of his absence and take over the Dark Fortress. An army of crusaders led by Catherine Ironfist set out from Steadwick. On the same day an army of elven snipers led by Gelu set out from the forests of AvLee. The commanders realize that infantry is vulnerable to liches, and the elven arrows are ineffective against the skeletons, hence the two armies should unite and attack the Fortress simultaneously. As Sandro may return any moment, the Fortress should be attacked as soon as possible. As a court cartographer, you are to calculate the number of days required to implement this plan.

Erathia is divided into square regions. Some of them are passable, some of them are not. On one day, each army can move to one of the adjacent (sharing a vertex with a current region) passable regions. Some of the Erathian passable regions have a teleport of one of 26 types inside. A type of a teleport is indicated by a capital Latin letter. If an army is located in a region with a teleport, it can move to any region with a teleport of the same type instantly. When two armies are located in the same region, they unite and then start to move as a single army. No army can attack the Fortress (that is, make a move to the region the Fortress is located in) before the union.

The first line contains space-separated integers n and m — dimensions of the map of Erathia (1 ≤ n, m ≤ 100). Then the map itself follows — n lines of m characters each. The meaning of the characters:
'#' indicates impassable region.
'.' indicates passable region.
'A'…'Z' indicates a teleport of type corresponding to that letter.
'$' indicates Catherine's army.
'!' indicates Gelu's army.
'*' indicates the Fortress.
It is guaranteed that the characters '*', '$', '!' are encountered exactly once on the whole map.

Output a single integer — the number of days that should pass before the united army can attack the Fortress. If the Fortress can't be attacked, output “Impossible”.