roflanka

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long
#define X first
#define Y second
#define ld long double
#define SZ(x) ((int)(x).size())
#define Pudger(i,a,n) for (int i=a;i<n;i++)
#define Pudge(i,n) Pudger(i,0,n)
#define Rudger(o,a,n) for (int o=n-1;o>=a;o--)
#define Rudge(o,a) Ror(o,0,a)
#define Sniper(axe,x) for (auto& axe: x)
#define Za_delo_beryotsa_myasnik ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define Ya_myasnik_a_ti_myasco freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef string ST;

const ld PI = 4*atan((ld)1);
const LL mod = 1e5 + 7;
const LL MAXN = 1e5+7;

template<class T>
istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }

template<class T>
istream& operator >> (istream& in, pair<T, T> & v){ in >> v.X >> v.Y;return in; }

template<class T>
ostream& operator << (ostream& out, pair<T, T> & v){ out << v.X << " " << v.Y;return out; }

template<class T>
ostream& operator << (ostream& out, vector<T> & v){ for (auto x : v) { out << x << " "; } return out; }

vector<int> mnoj(int pudge){
    int i = 2;
    vector<int> a;
    while(i*i < pudge){
        while(pudge % i == 0){
            pudge /= i;
            a.pb(i);
        }
        i++;
    }
    if(pudge>1)
        a.pb(pudge);
    return a;
}

int Binsearch(VI &a,int x){
    int hight, low, mid;
    hight = SZ(a)-1;
    low = 0;
    Pudge(i,1000){
        mid = (hight+low)/2;
        if(a[mid]>=x){
            hight = mid;
        }
        else
            low = mid;
    }
    return low;
}

ST str, tmp, st;
int n,d = -1, cur,k,g,g1,cnt,b,k1 = -1,b1 = -1, cnt1, nn, kk, bb, m, ans12 = 0;
queue<pair<int, int>> ark;

main(){
    Za_delo_beryotsa_myasnik;
    //Ya_myasnik_a_ti_myasco
    cin >> n >> m;
    vector<vector<char>> graph(n, vector<char>(m));
    vector<VI> used(n, vector<int>(m));
    vector<vector<PII>> ans(n, vector<PII>(m));
    vector<VI> dist(n, VI(m));
    vector<PII> arka{
        { 1,0 },
        { -1,0 },
        { 0,1 },
        { 0,-1 }
    };

    Pudge(i,n){
        Pudge(j,m){
            dist[i][j] = -1;
            cin >> graph[i][j];
            if(graph[i][j] == '*'){
                k = i;
                b = j;
            }

        }
    }
    cin >> nn;
    vector<PII> belmandoe;
    Pudge(i,nn){
        cin >> kk >> bb;
        kk--;
        bb--;
        belmandoe.pb(make_pair(kk,bb));
        graph[kk][bb] = 'X';
    }
    ark.push(make_pair(k,b));
    used[k][b] = 1;
    while(!ark.empty()){
        g = ark.front().X;
        g1 = ark.front().Y;
        ark.pop();
        Pudge(i,4){
            if( (0 <= g + arka[i].X) and ( g + arka[i].X < n) and (0 <= g1 + arka[i].Y) and (g1 + arka[i].Y< n) ){
                if( graph[ arka[i].X + g ][ g1 + arka[i].Y ] == '0'){
                    if(!used[ g + arka[i].X ][ g1 + arka[i].Y ]){
                        used[ g + arka[i].X ][ g1 + arka[i].Y ] = 1;
                        ark.push(make_pair(g + arka[i].X , g1 + arka[i].Y));
                        ans[ g + arka[i].X ][ g1 + arka[i].Y ] = make_pair(g,g1);
                        dist[ g + arka[i].X ][ g1 + arka[i].Y ] = dist[g][g1]+1;
                    }
                }
                if( graph[ arka[i].X + g ][ g1 + arka[i].Y ] == 'X'){
                    k1 = g+arka[i].X;
                    b1 = g1+arka[i].Y;
                    used[ arka[i].X + g ][ g1 + arka[i].Y ] = 1;
                    ans[ arka[i].X + g ][ g1 + arka[i].Y ] = make_pair(g,g1);
                    dist[ g + arka[i].X ][ g1 + arka[i].Y ] = dist[g][g1]+1;
                }
            }
        }
    }
    if(k1<0 and b1<0){
        cout << -1;
        return 0;
    }
    int mih = 101;
    Pudge(i,nn){
        if(dist[belmandoe[i].X][belmandoe[i].Y]<mih and dist[belmandoe[i].X][belmandoe[i].Y] != -1){
            mih = dist[belmandoe[i].X][belmandoe[i].Y];
            d = i;
        }
    }
    cout << d+1;
    return 0;

}