Hide

Problem G
Hurricane Danger!

Hurricanes can cause a lot of destruction when they pass over land. Given the path that a hurricane takes and the locations of a number of cities, find which city is in the most danger of damage. That is, the city that is closest to the path the hurricane takes. Assume that each hurricane travels in a straight line, and that it has been traveling for a long time and will continue to do so for a long time.

Input

The first line of input contains an integer $1 \le n \le 500$ indicating the number of test cases that follow. Each case starts with a line containing four integers $x_1~ y_1~ x_2~ y_2$ indicating the coordinates of the two different locations the hurricane was already spotted. The second line contains an integer $1 \le m \le 100$ indicating the number of cities for that case. The following $m$ lines each contain a unique city name ($1$ to $20$ characters from a–z) and two integers indicating the $x$ and $y$ coordinates of that city. All coordinates are in the range $[0, 1\, 000]$.

Output

For each set of cities, print the name of the city that is in the greatest danger. If more than one city is considered in greatest danger, print them all separated by spaces in the order they appear in the input.

Sample Input 1 Sample Output 1
2
1 1 2 1
3
Waco 5 3
Lafayette 5 2
Knoxville 7 4
3 3 10 10
3
Tampa 5 5
Rochester 12 12
Duluth 15 16
Lafayette
Tampa Rochester

Please log in to submit a solution to this problem

Log in