Kryptonite Mine

In the year 2222 a terrible disaster struck a kryptonite mine on Mars: a marsquake shook that part of the planet. Unlike earthquakes on 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 outer shape, and its interior is a maze of high, straight walls and — most importantly — teleporters. Teleporters can move a person instantly from one place to another. The teleporters in this mine are old models built with ancient technology, so they can move a person between two booths only if there is a clear line of sight from one booth to the other (that is, no wall lies strictly between the two booths).

You are trapped alone inside the mine. Fortunately you have a map of the whole mine and you know your current location, the positions of the walls, the location of the exit, and the location of every teleporter booth. Unfortunately the marsquake damaged the power system, so the teleporters can be used only a limited number of times in total.

Because you sprained your ankle during the marsquake, you want to reach the exit while walking as little as possible. You cannot walk through a wall — you must go around it. Find the route from your current location to the exit that minimizes the total walking distance.

The input contains several test cases. The first line of each test case has three integers $N$, $M$ and $L$: the number of times the teleporters may be used in total, the number of walls in the mine, and the number of teleporter booths ($0 \le N, M, L \le 50$).

Each of the next $M$ lines has four integers $X_1$, $Y_1$, $X_2$, $Y_2$, the coordinates of the two endpoints of a wall. Walls have no thickness and no two walls intersect ($-20000 \le X_1 \le X_2 \le 20000$ and $-20000 \le Y_1 \le Y_2 \le 20000$).

Each of the next $L$ lines has two integers $X_p$ and $Y_p$, the coordinates of a teleporter booth.

The last line of each test case has four integers $X_b$, $Y_b$, $X_e$, $Y_e$, where $(X_b, Y_b)$ is your starting location and $(X_e, Y_e)$ is the mine's exit.

The end of the input is a line with $N = M = L = 0$, which must not be processed.

For each test case, print a single line with one integer: the minimum distance you must walk to get out of the mine. Distances covered by teleporting do not count. The distance must be rounded to the nearest integer.