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

int W, H;
char G[1001][1001];
int vis[1001][1001];

bool bfs(int x, int y) {
  const static int dx[] = {1,0,-1,0};
  const static int dy[] = {0,1,0,-1};
  queue<int> que;
  que.push(x+y*W);
  while(!que.empty()) {
    x = que.front()%W;
    y = que.front()/W;
    que.pop();
    for(int i = 0; i < 4; ++i) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || nx >= W) continue;
      if(ny < 0 || ny >= H) continue;
      if(vis[ny][nx]) continue;
      if(G[ny][nx] == '#') {
	vis[ny][nx] = 1;
	continue;
      }

      if(G[ny][nx] == 't') return true;
      que.push(nx+ny*W);
      vis[ny][nx] = 2;
    }
  }
  return false;
}

int main() {
  cin >> W >> H;
  for(int i = 0; i < H; ++i) {
    for(int j = 0; j < W; ++j) {
      cin >> G[i][j];
    }
  }

  int N;
  cin >> N;
  int x, y;
  x = y = 0;
  for(int i = 0; i < H; ++i) fill(vis[i],vis[i]+W,0);
  vis[0][0] = 1;
  int ans = -1;
  for(int i = 0; i <= N; ++i) {
    if(ans == -1 && vis[y][x] == 1 && bfs(x,y)) ans = i;
    if(i != N) {
      cin >> x >> y;
      if(G[y][x] == '#') G[y][x] = '.';
    }
  }
  cout << ans << endl;
  return 0;
}