Woburn Challenge 1998

Like we said earlier, Luke Skywalker is a wimp and so Yoda is having a really hard time turning him into a worthy Jedi Knight. His first lesson is in the Bogs of Endor, a large swamp that has several solid surfaces in various places. Luke can only stand on one of the solid surfaces, otherwise he will sink into the swamp and be eaten by a really disgusting looking creature (and Yoda won't be too pleased with that). His training exercise consists of the following. Yoda will place him on one of the solid surfaces to start. He must then use the power of the Force to jump between solid surfaces till he reaches Yoda, who is on another solid surface some distance away. Luke is still a Young Jedi, so his jumping range is limited. Yoda is an impatient "man" and so Luke must find the quickest way to get to Yoda.

Input Specification

You will be given a ~k \times n~ grid (total grid size ~\le 32\,000~) representing the swamp. Each point in the grid will be marked either * (representing a solid surface) or the letter o representing no solid surface. You will also be told of Luke's starting point and Yoda's position. You will also be given the maximum distance that Luke can jump.

All inputs will be integers in the range ~1 \le \text{number} \le 32\,000~.

Line 1: ~k~
Line 2: ~n~
Line 3: Luke's maximum jumping distance
The next ~k~ lines will contain the grid (~n~ characters on each line). Note that the topleft corner of the grid is at coordinate ~(1, 1)~.
The next line will contain Luke's starting position as ~x_0~ ~y_0~ (separated by one space).
The next line will contain Yoda's position as ~x_1~ ~y_1~ (separated by one space).
You will then be given more pairs of lines giving new positions for Luke and Yoda. The input will be terminated by a single line containing -1 -1 (i.e. starting coordinates are ~(-1, -1)~).

Output Specification

You will output the smallest number of jumps that Luke needs to make to reach Yoda from where he is for each starting position (each one on a separate line). If he cannot reach Yoda, then output THERE IS NO TRY.

Sample Input

5
5
2
oooo*
ooo*o
oo*o*
ooo**
*ooo*
5 1
1 5
5 5
1 5
-1 -1

Sample Output

THERE IS NO TRY
2