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 <string>
#include <queue>
#include <vector>
#define INF 100000000
#define dis first
#define x second.first
#define y second.second
using namespace std;
typedef pair < int ,pair < int,int > > P;
int mp[1001][1001];
int D[1001][1001];
int w,h,tx,ty;
int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
int dijkstra(){
  priority_queue <P, vector<P>, greater<P> > Q;
  for(int i=0;i<=h;i++)
    for(int j=0;j<=w;j++) D[i][j] = INF;
  D[0][0] = 0;
  P t,a;
  t.dis = t.x = t.y = 0;
  Q.push(t);
  while(!Q.empty()){
    t = Q.top();Q.pop();
    if(t.x == tx && t.y == ty) return t.dis;
    for(int i=0;i<4;i++){
      int nx = t.x+dx[i];
      int ny = t.y+dy[i];
      if(nx<0 ||ny<0 ||nx>=w ||ny>=h || mp[ny][nx] == INF)continue;
      int ndis = max(t.dis,mp[ny][nx]);
      if(ndis < D[ny][nx]){
	a.dis = ndis , a.x = nx , a.y = ny;
	Q.push(a);
	D[ny][nx] = ndis;	
      }
    }
  }
  return -1;
}

int main(){
  while(cin >>w >>h){
    string str;
    for(int i=0;i<h;i++){
      cin >> str;
      for(int j=0;j<w;j++)
	if(str[j] == '.') mp[i][j] = 0;
	else if(str[j] =='#') mp[i][j] = INF;
	else if(str[j] == 't') mp[i][j] = 0,tx =j,ty = i;
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++){
      int a,b;
      cin >> a >> b;
      if(mp[b][a] == INF)  mp[b][a] = i;
    }
    cout << dijkstra() <<endl;
  }
  return 0;
}