Matcom Online Grader

In the year of 2222, a terrible disaster happened at the kryptonite mine in Mars: a marsquake shook that part of the planet. Differently from earthquakes in Earth, marsquakes are not unusual on Mars. This one, however, caused the mine to start sinking slowly into the soil. The mine has a rectangular external shape, and its interior is like a maze, with high, straight walls and, most importantly, teleporters. Teleporters, as you know, can transport people instantly from one place to another. Teleporters in the mine are old models, using ancient technology, and can only teleport people if there is a clear view from one teleporter booth to another (that is, if there are no obstacles or walls in between the booths). You can see the map of the mine in the figure below.

The input consists of many test cases. The first line of a test case contains three integers $N$, $M$ and $L$, which indicate, respectively, the number of times the teleporters can be used, the number of walls in the mine and the number of teleporter booths $(0 \leq N, M, L \leq 50)$. Each of the next $M$ lines contains four integers $X_1, Y_1, X_2$ and $Y_2$, which represent the coordinates of the endpoints of a wall. You may ignore the thickness of walls and assume they do not intersect each other ($-20000 \leq X_1 \lt X_2 \leq 20000$ and $-20000 \leq Y_1 \lt Y_2 \leq 20000$). The next $L$ lines contain the location of teleporter booths, given by two integers $X_p$ and $Y_p$. The last line of each test case contains four integers $X_b$, $Y_b$, $X$ e and $Y$ e where $(X_b, Y_b)$ are the coordinates of your location and $(X_e, Y_e)$ are the coordinates of the mine's exit. The end of input is indicated by $M=N=L=0$.

For each test case in the input your program must output a single line, containing an integer representing the distance you need to walk to get out of the mine. Of course, you should not consider the distances you teleported.The distance must be rounded to the nearest integer.