Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2
#include<iostream>
using namespace std;

int mp[1000000];
int w,h,t;
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

int find(int x){
 if(x==mp[x])return x;
 else{
   mp[x]=find(mp[x]);
   return mp[x];  
 }
}

void unite(int x,int y){
 x=find(x),y=find(y);
 if(x<y)swap(x,y);
 mp[x]=y; 
}

int solve(){
 int n,x,y;
 cin>>n;
 if(find(t)==0)return 0; 
 for(int i=1;i<=n;i++){
   cin>>x>>y;
   int k=y*w+x;
   if(mp[k]==-1){
     mp[k]=k;
     for(int j=0;j<4;j++){
     int nx=x+dx[j],ny=y+dy[j];
     if(nx<0||ny<0||w<=nx||h<=ny||mp[ny*w+nx]==-1)continue;
     unite(ny*w+nx,k);
   }
   if(find(t)==0)return i;
   }
 }
 return -1;
}

int main(){
 char c;
   cin>>w>>h;
   for(int i=0;i<h;i++)
     for(int j=0;j<w;j++){
   mp[i*w+j]=i*w+j;
   cin>>c;
   if(c=='#')mp[i*w+j]=-1;
   if(c=='t')t=i*w+j;
   if(c=='.'||c=='t')
     for(int k=0;k<2;k++)
       if(0<=dy[k]+i&&0<=j+dx[k]&&mp[(dy[k]+i)*w+j+dx[k]]!=-1)
         unite((dy[k]+i)*w+j+dx[k],i*w+j);
     }
   cout<<solve()<<endl;
 return 0;
}