Узнав, что лич Сандро ушёл воевать с королём демонов, эрафийские военачальники решили воспользоваться его отсутствием и захватить Тёмную крепость. Из Стедвика вышла армия крестоносцев во главе с Катериной Айронфист. В тот же день из лесов АвЛи им на помощь вышла армия эльфов-снайперов под предводительством легендарного стрелка Джелу. Военачальники прекрасно понимают, что пехота уязвима для личей, а стрелы эльфов крайне неэффективны против скелетов, поэтому двум армиям нужно объединиться и напасть на крепость одновременно. И поскольку Сандро может вернуться в любой момент, Тёмная крепость должна быть атакована как можно раньше. Вас же, как придворного картографа, попросили посчитать, какое минимальное количество дней уйдёт на реализацию этого плана.

Эрафия поделена на квадратные районы. Некоторые из них проходимы, некоторые — нет. За один день каждая армия может перейти в любой из 8 соседних (имеющих общую вершину) районов, если он проходим. В некоторых проходимых районах Эрафии установлен телепорт одного из 26 типов. Тип телепорта обозначается заглавной латинской буквой. Если армия располагается в районе с телепортом, то она может мгновенно переместиться в любой район с телепортом того же типа. В тот момент, когда обе армии оказываются в одном районе, они объединяются и далее перемещаются как единое целое. До объединения ни одна из армий не может нападать на крепость Сандро, то есть делать ход в район, в котором расположена крепость.

В первой строке через пробел записаны числа n и m — размеры карты Эрафии (1 ≤ n, m ≤ 100). Далее задана сама карта — n строк по m символов в каждой. Символы имеют следующий смысл:
'#' — непроходимый район.
'.' — проходимый район.
'A'…'Z' — телепорт соответствующего типа.
'$' — армия Катерины.
'!' — армия Джелу.
'*' — крепость Сандро.
Гарантируется, что символы '*', '$', '!' встречаются на карте ровно один раз.

Выведите единственное число — минимальное количество дней, через которое объединённая армия сможет напасть на крепость Сандро. Если нападение совершить невозможно, выведите «Impossible».