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<set>
#include<stack>
#define pb push_back
#define sz size()
#define For(i,a) for(int i=0;i<(int)a;i++)
using namespace std;

typedef pair<int,int> P;

string grid[1100];
bool v[1100][1100];
int w,h,n;
stack<P> q;
set<P> s;

bool dfs(int y,int x){
  q.push(P(y,x));

  while(q.size()){
    int y = q.top().first, x = q.top().second;
    q.pop();
    
    if(grid[y][x] == 't')return true;
    
    v[y][x] = true;
    int dy[] = {-1,0,1,0},dx[] = {0,1,0,-1};
    
    For(i,4){
      int sy = y + dy[i] , sx = x + dx[i];
      if(sy<0 || sx<0 || h<=sy || w<=sx || v[sy][sx])continue;
      if(grid[sy][sx] == '#'){
	s.insert(P(sy,sx));
	continue;
      }
      q.push(P(sy,sx));
    }
  }
  return false;
}

int main(){
  int x,y;
  cin >> w >> h;

  For(i,h)cin >> grid[i];
  For(i,h)For(j,w)v[i][j] = false;

  while(q.sz)q.pop();
  s.clear();

  if(dfs(0,0))cout << 0 << endl;
  else{
    cin >> n;
    For(i,n){
      cin >> x >> y;
      if(grid[y][x]=='#'){
	grid[y][x] = '.';

	int s1 = s.sz;
	s.insert(P(y,x));
	int s2 = s.sz;
	s.erase(P(y,x));
	if(s1==s2){
	  if(dfs(y,x)){
	    cout << i+1 << endl;
	    return 0;
	  }
	}
      }
    }
    cout << -1 << endl;
  }
}