# GPS Reverse Positioning

Time Limit: 5 Seconds    Memory Limit: 32768 KB

Given the map data and the information seen on the screen, your job is to find all locations on the map which are possibly your current position.
The points of interest seen on the screen are also given as some nodes of the map. Though, your current position is not necessarily on a node of the map; in this case, you are on a road. The shortest-path distances given on the screen are calculated according to the rules specified above.

## Input

The input contains several test cases. Each test case starts with a line containing three space-separated integers N (1 <= N <= 10000), the number of nodes, R (1 <= R <= 10000), the number of roads, and M (1 <= M <= 1000), the number of the points of interest. The nodes are numbered 1, 2, ..., N. The next N lines specify the coordinates of the nodes. The ith line of this part contains two space-separated integers xi and yi (-105 <= xi, yi <= 105), the coordinates of node i. Then, R lines follow, each with two space-separated integers ui and vi, indicating that the two nodes ui and vi are connected by a road. It is guaranteed that the road is either vertical (xui = xvi) or horizontal (yui = yvi). The test case ends with M lines specifying the information available on the GPS system screen. Each of these lines has two space-separated integers wi and di (0 <= di <= 109), where wi is the number of a node as a point of interest, and di is the distance from your current position to node wi.
The input ends with a line of the form "0 0 0" (omit the quotes) which should not be processed as a test case.

## Output

For each test case, you should first write a line containing a single integer k, the number of distinct points on the map that might be your current position. Then, on each of the next k lines, you should write two space-separated integers Xi and Yi as the  coordinates of one of the possible points. The coordinates must be in ascending order based on their Xi’s, and then by their Yi’s (when their Xi’s are equal).

```7 6 2
0 1
1 0
1 1
1 3
3 1
3 3
4 0
1 3
3 5
5 6
4 3
3 2
2 7
7 5
5 3
3 2 1
0 0
2 0
3 0
1 2
1 3
1 1
3 2 1
0 0
0 2
0 0
1 2
2 3
1 3
3 2 2
0 0
0 2
0 0
1 2
2 3
1 3
3 3
0 0 0
```

## Sample Output

```2
0 1
1 2
1
1 0
1
0 1
0
```
Submit

Source: Tehran, Asia Region - Regional 2011