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 <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> P;

int w, h;
int gx, gy;
char t[1002][1002];
bool flg[1002][1002];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool solve(int sx, int sy){
  queue<P> open;
  open.push(P(sx, sy));

  while(!open.empty()){
    P p = open.front(); open.pop();
    if(flg[p.second][p.first]) continue;
    flg[p.second][p.first] = true;

    if(p.first == gx && p.second == gy){
      return true;
    }

    for(int i = 0; i < 4; i++){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];

      if(nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
      if(t[ny][nx] == '#') continue;
      open.push(P(nx, ny));
    }
  }

  return false;
}

int main(){
  while(cin >> w >> h){
    for(int i = 0; i < h; i++){
      cin >> t[i];

      for(int j = 0; j < w; j++){
        if(t[i][j] == 't'){
          gx = j;
          gy = i;
          t[i][j] = '.';
        }
      }
    }

    int ans = -1;
    memset(flg, 0, sizeof(flg));
    if(solve(0, 0)) ans = 0;

    int T;
    cin >> T;

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

      if(0 <= ans) continue;

      t[y][x] = '.';

      for(int j = 0; j < 4; j++){
        int nx = x + dx[j];
        int ny = y + dy[j];
        if(nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
        if(flg[ny][nx]){
          bool tmp = solve(x, y);
          if(tmp) ans = i + 1;
          break;
        }
      }
    }

    cout << ans << endl;
  }
}