Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

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


Output

2
#include<iostream>
#include<stack>
#include<utility>
using namespace std;

typedef pair<int,int> P;

int w,h,n;
string grid[1010];
bool vis[1010][1010];
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};

void dfs(int y,int x){
  stack<P> s;
  s.push(P(y,x));
  vis[y][x] = true;

  while(s.size()){
    P p = s.top(); s.pop();

    for(int i=0;i<4;i++){
      int ty = p.first + dy[i], tx = p.second + dx[i];
      if(ty<0 || tx<0 || h<=ty || w<=tx || grid[ty][tx] == '#')continue;
      if(!vis[ty][tx]){
	vis[ty][tx] = true;
	s.push(P(ty,tx));
      }
    }
  }
}

int main(){
  int gy,gx,x,y;
  cin >> w >> h;
  for(int i=0;i<h;i++){
    cin >> grid[i];
    for(int j=0;j<w;j++){
      vis[i][j] = false;
      if(grid[i][j] == 't'){
	gy = i;
	gx = j;
      }
    }
  }

  dfs(0,0);

  if(vis[gy][gx]){
    cout << 0 << endl;
    return 0;
  }

  cin >> n;
  for(int i=0;i<n;i++){
    cin >> x >> y;

    grid[y][x] = '.';
    for(int j=0;j<4;j++){
      if(y+dy[j]<0 || x+dx[j]<0 || h<=y+dy[j] || w<=x+dx[j])continue;
      if(vis[y+dy[j]][x+dx[j]])dfs(y,x);
    }
 

    if(vis[gy][gx]){
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}