1643TLE27

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<vector<char> >g;
vector<vector<bool> >used;
vector<vector<int> > d;
vector<vector<pair<int,int> > >  t;
int n,m;
int res1=-1,res2=-1;
int dx[] = {-1, -1, -1,  0, 1, 1,  1,  0};
int dy[] = {-1,  0,  1,  1, 1, 0, -1, -1};
int bfs(int x, int y){
    queue<pair<int,int> > q;
    q.push({x,y});
    while(!q.empty()){

        pair<int,int> to=q.front();
      /*  if(to.first==2 && to.second==0){
            cout<<"=="<<d[to.first][to.second]<<endl;

        }*/

       //cout<<to.first<<' '<<to.second<<endl;
       //cout<<used[0][6]<<' '<<endl;
        used[to.first][to.second]=1;
        if(g[to.first][to.second]=='!'){
            res1=d[to.first][to.second];
        }
        if(g[to.first][to.second]=='$'){
            res2=d[to.first][to.second];
        }
        q.pop();
         if(isalpha(g[to.first][to.second])){
                for(int h=0; h<t[g[to.first][to.second]-'A'].size(); h++){
                pair<int,int> newto=t[g[to.first][to.second]-'A'][h];
                if(!used[newto.first][newto.second]){
                    q.push({newto.first,newto.second});
                  //cout<<newto.first<<newto.second<<' '<<to.first<<to.second<<endl;
                  //cout<<d[to.first][to.second]<<endl;
                  used[newto.first][newto.second]=1;
                    d[newto.first][newto.second]=d[to.first][to.second];
                  //  cout<<d[newto.first][newto.second]<<' ';
                }
         }
         }

        for(int i=0; i<8; i++){
            pair<int,int> cop=make_pair(to.first+dx[i], to.second+dy[i]);
                if(cop.first>=0 && cop.first<n && cop.second>=0 && cop.second<m && g[cop.first][cop.second]!='#'){
                    if(!used[cop.first][cop.second]){
                    q.push(cop);
                    used[cop.first][cop.second]=1;
                    d[cop.first][cop.second]=d[to.first][to.second]+1;
                         }
                    else{
                        if(d[cop.first][cop.second]>d[to.first][to.second]+1){
                            d[cop.first][cop.second]=d[to.first][to.second]+1;
                        }
                    }
            /*if(cop.first==2 && cop.second==0){
            cout<<"=="<<d[cop.first][cop.second]<<endl;*/


            }
        }
    }
    if(res1==-1 || res2==-1) return -1;
    return(max(++res1,++res2));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
     t.resize(30,vector<pair<int,int> >());
    g.resize(n,vector<char>(m));
    d.resize(n,vector<int> (m));
    used.resize(n,vector<bool>(m,0));
    char a;
    pair<int,int> kate,jelo,krep;
    string str;
    for(int i=0; i<n; i++){
        cin>>str;
        for(int j=0; j<str.size(); j++){
            g[i][j]=str[j];
            if(str[j]=='$') kate={i,j};
            else if(str[j]=='!') jelo={i,j};
            else if(str[j]=='*'){ krep={i,j};
            g[i][j]='#';
            }
            else if(isalpha(str[j]))
                t[g[i][j]-'A'].emplace_back(i,j);
        }
    }


        vector<int>ans;
    for(int i=0; i<8; i++){
        pair<int,int> v=make_pair(krep.first+dx[i],krep.second+dy[i]);
        if(v.first>=0 && v.first<n && v.second>=0 && v.second<m && g[v.first][v.second]!='#'){
            ans.pb(bfs(v.first,v.second));
             d.assign(n,vector<int>(m,0));
             used.assign(n,vector<bool>(m,0));
        }
    }
    int mn=1e9;
    for(int i=0; i<ans.size(); i++){
        if(mn>ans[i])
            mn=ans[i];
    }
    if(mn==-1 || mn==1e9)
        cout<<"Impossible";
    else cout<<mn;



    return 0;
}