Lucky Dip

Time Limit: 8 sec / Memory Limit: 64 MB

C: 福袋

福袋，それは年始を祝う商習慣の一つである． 人気の福袋には多くの人が開店前から行列を作り，ターゲットの福袋へダッシュする． この風物詩に魅了されたあなたは，今年もお目当ての福袋を狙い，計画を立てていた．

しかし，お客を呼び寄せる側の某百貨店の店長は頭を悩ませていた． どうやらフロアの準備が開店に間に合いそうにない．

そこで店長はある一つのアイディアを思いついた． それは開店後，店内を徐々に開放すればなんとか営業できるのではないかというものである．

あなたは刻一刻と変化する店内の情報を元に，お目当ての福袋がどの時間帯から入手できるのかを調べたい．

Input

入力は単一のデータセットで与えられ，EOFで終了する．

店内の様子は各行が W 文字からなる H 行の文字列で表される．

1 行目

W H
2 < W, H <= 1000

続く H 行

店内の様子

• .: 床
• #: 壁
• t: 目的の福袋

目的の福袋は店内に必ず1つだけ存在する．

H + 2 行目

営業時間 N (0 <= N <= 1000)

続く N 行

x1 y1
x2 x2
...
xi yi
...
xn yn

(x_i, y_i)は，i 時間目に開放される壁の座標を表す．(0 <= x_i < W, 0 <= y_i < H)
x_i が列，y_i が行である．
開放される壁の座標の位置が "#" なら "." に置き換え，"." なら何もしない．
目的の福袋が開放されることはない．
(0, 0) が壁になることはない．

またあるマスからの移動は，上下左右の4方向のマスへのみが可能であり，壁の上へ移動することはできないものとする．

Output

左上(0, 0) から t の座標へ辿りつけるようになる時間 s (-1 <= s <= N)を1行で出力せよ．
壁を開放せずに辿りつける場合，0 を出力せよ．
営業時間が終了しても到達できなければ -1 を出力すること．

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

-1

---