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 <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
  
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
  
using namespace std;
  
typedef pair<int, int> P;
  
int W, H, N;
char field[1002][1002];
  
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int open[1002][1002];
bool visit[1001][1001];

int bfs(){
    priority_queue<pair<int, P>, vector<pair<int, P> >, greater<pair<int, P> > > q;
    q.push(MP(0, MP(0, 0)));
  
    while(!q.empty()){
		int t = q.top().first;
		P p = q.top().second;
        q.pop();

        if(visit[p.second][p.first]) continue;
        visit[p.second][p.first] = true;
  
        if(field[p.second][p.first] == 't') return t;
  
        rep(i, 4){
            int nx = p.first+dx[i], ny = p.second+dy[i];
            if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
			if(field[ny][nx] != '#') q.push(MP(t, MP(nx, ny)));
			else if(open[ny][nx] != 0) q.push(MP(max(t, open[ny][nx]), MP(nx, ny)));

        }
    }
  
    return -1;
}
  
int main(){
	cin >> W >> H;
    rep(i, H) rep(j, W) cin >> field[i][j];
    cin >> N;
	memset(open, 0, sizeof(open));
    rep(i, N){
        int x, y;
        cin >> x >> y;
		if(field[y][x] == '#' && !open[y][x]) open[y][x] = i+1;
    }
	cout << bfs() << endl;
  
    return 0;
}