Crossing Streets EXTREME

Input: Standard Input

Output: Standard Output

Many of you probably know Peter Longfoot, who was a student in University of Suburbia in 2005. He does not like crowded streets so in World Finals 2005 in Shanghai, contestants wrote a program for him that helped him find the path from his home to his university that required least crossing of streets. But in Suburbia streets were drawn as horizontal or vertical lines. Now Peter has become a student of University of Chingchuk. The streets of Chingchuk be can drawn as straight line but they are not necessarily horizontal or vertical as shown in picture below. Also not all streets are equally crowded. If there is a place near a street that can cause a lot of crowd (such as super markets or railway stations) then the road segments adjacent to it will become more crowded and so peter may want to avoid them also if possible.


Figure 1: The green arrow shows one optimal path to go from A to B. The red arrow and magenta arrow show two possible invalid paths. The red path is invalid because walking through the crossing of two or more streets is not allowed and the magenta path is invalid because walking along the street is invalid.	Figure 2: The square marked places are crowded places. The crowded place at (1,1) has crowding index 5 and the crowded place at (1,7) has crowding index 10. So now the new minimum cost path from A to B is shown in dark green. Red color denotes the streets whose costs have been increased due to crowded places.

Figure 1 has four streets. If Peter’s house is at A and his University is at B then he requires crossing minimum two streets. By default the cost of crossing a street is 1 so his total cost of reaching his university is 2. Peter never walks through a street crossing and also he never walks along the street. In Figure 2 there are two crowded places, one at C(1, 1) and the other at D(1,7). The crowding index of C is 5 and the crowding index of D is 10. So now the road segments adjacent to C has crossing cost (5+1)=6 and the road segments adjacent to D has crossing cost (1+10)=11. A road segment is adjacent to a crowded place if that road segment can be reached from the crowded place without crossing any other street. Given the road map of Chingchuk, the coordinate of Peter’s home and university and the coordinate and crowding index of the crowded places your job is to find the minimum cost that Peter needs to reach his university.

Input

The input file contains at most 100 sets of inputs. Most cases are not extreme (N is much less than 40). The description of each set is given below:

First line of each set contains three integers N (2 ≤ N ≤ 35), C (0 ≤ C ≤ 1000) and Q (0 ≤ Q ≤ 10). The integer N indicates how many streets are there, C indicates the number of crowded places and Q indicates the total number of queries. Each of the next N lines contains three integers (1 ≤ i ≤ N and 0 ≤≤ 1000000 and both a and b will never be zero) which indicates that the equation of the i-th street is . Each of the next C lines contains three integers. This means that there is a crowded place at location and it increases the crossing costs of adjacent road segments by(1 ≤≤ 20). Each of the next Q lines contains four integers, which implies that for that specific query the coordinate of Peter’s home is and the coordinate of Peter’s university is . You can assume that Peter’s home, Peter’s University and the crowded places are never situated on a street and also no two streets are parallel two each other. You can also assume that absolute values of all coordinates are not greater than 1000.