ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Autumn school contest 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Attack of the Dark Fortress

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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

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”.

Samples

inputoutput
5 8
....AA.#
.######!
.....*##
.#######
..B$...B
11
3 5
##*..
!#...
##..$
Impossible
Problem Author: Denis Dublennykh
Problem Source: USU Junior Contest, October 2008
To submit the solution for this problem go to the Problem set: 1643. Attack of the Dark Fortress