OpenKattis
Set #11

#### Start

2018-04-04 05:00 AKDT

## Set #11

#### End

2018-04-11 04:59 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1171 days 20:33:56

167:59:59

0:00:00

# Problem FHurricane 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