Time Limit: 8 sec / Memory Limit: 64 MB





Example

Input

10 10
.....#....
.....#....
.....#....
######....
..........
####......
....###...
t..#..####
...##.....
....#...##
3
0 3
0 5
4 6


Output

2
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
const int MN = 1010;
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool g[MN][MN] = {};
int main() {
    int w, h;
    int tx, ty;
    cin >> w >> h;
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            if (s[j] == 't') {
                tx = i; ty = j;
            }
            if (s[j] == '#') {
                g[i][j] = true;
            }
        }
    }
    bool used[MN][MN];
    fill_n(used[0], MN*MN, false);
    int n;
    cin >> n;
    queue<P> q;
    q.push(P(0, 0));
    bool f = false;
    for (int i = 0; i <= n; i++) {
        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front(); q.pop();
            if (used[x][y]) continue;
            used[x][y] = true;
            if (x == tx && y == ty) {
                f = true;
                break;
            }
            for (int j = 0; j < 4; j++) {
                int x2 = x, y2 = y;
                x2 += d[j][0];
                y2 += d[j][1];
                if (0 <= x2 && x2 < h && 0 <= y2 && y2 < w && !g[x2][y2]) {
                    q.push(P(x2, y2));
                }
            }
        }
        if (f) {
            printf("%d\n", i);
            return 0;
        }
        if (i == n) break;
        int x, y;
        cin >> y >> x;
        g[x][y] = false;
        for (int j = 0; j < 4; j++) {
            int x2 = x, y2 = y;
            x2 += d[j][0];
            y2 += d[j][1];
            if (0 <= x2 && x2 < h && 0 <= y2 && y2 < w && used[x2][y2]) {
                q.push(P(x, y));
                break;
            }
        }
    }
    printf("-1\n");
    return 0;
}