Follow the Pair

A travel blogger pins known places on a city map. Each place has a label like ramen, tacos, or pizza. When the blogger stands at a new spot, they ask the three closest locals. If the two second-closest locals agree with each other but disagree with the very closest local, the blogger trusts the pair; otherwise, use a normal 3-nearest-neighbors vote. Distances are straight-line Euclidean (L2).

The first line of the input contains a single integer n representing the number of known places.

The next n lines contain two floating-point numbers x y followed by a label word for that place.

The next line contains a single integer q representing the number of spots to check.
The last q lines contain two floating-point numbers x y for the blogger’s spot.

For each spot, the program should print the place that the blogger will go to. If distances tie when choosing neighbors, take the one that appears earlier in the input. If neighbor #2 and neighbor #3 share the same label and it is different from neighbor #1’s label, output that shared label. Otherwise, output the label with the highest count among the three; if the vote ties, print the alphabetically smallest label.