Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

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


Output

2
#include <set>
#include <cstdio>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

using namespace std;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int w, h;
char g[1000][1012];
bool reach[1000][1000];

int bfs(int x, int y){
  queue<pair<int, int> > q;
  q.push(make_pair(x, y));

  while(q.size()){
    pair<int, int> data = q.front(); q.pop();
    int xx = data.first;
    int yy = data.second;

    REP(i,4){
      int xxx = xx + _dx[i];
      int yyy = yy + _dy[i];
      if(ISIN(xxx, yyy, w, h) &&
         g[yyy][xxx] == '.' &&
         !reach[yyy][xxx]){
        reach[yyy][xxx] = true;
        q.push(make_pair(xxx, yyy));
      }
    }
  }

  return 0;
}

int main(){
  const int inf = 100000;
  int gx, gy;
  int ans = inf;
  scanf("%d%d", &w, &h);

  REP(i,h) scanf("%s", g[i]);
  REP(i,h) REP(j,w){
    if(g[i][j] == 't'){
      g[i][j] = '.';
      gx = j; gy = i;
    }
  }

  reach[0][0] = true; bfs(0, 0);
  if(reach[gy][gx]) ans = 0;

  int n;
  scanf("%d", &n);
  REP(i,n) if(ans == inf){
    int x, y; scanf("%d%d", &x, &y);
    if(g[y][x] == '#'){
      g[y][x] = '.';
      REP(j,4){
        int xx = x + _dx[j];
        int yy = y + _dy[j];
        if(ISIN(xx, yy, w, h) && reach[yy][xx]){
          reach[y][x] = true;
          bfs(x, y);
          break;
        }
      }
      if(reach[gy][gx]){
        ans = i + 1;
      }
    }
    // REP(i,h){ REP(j,w) printf("%d", reach[i][j]); puts(""); }
  }
  if(ans == inf) ans = -1;
  printf("%d\n", ans);

  return 0;
}