Ask Three Neighbors

A new café wants to match the neighborhood vibe. It knows where other cafés are and what roast they serve: light, medium, or dark. For each possible location, it will ask the three closest cafés and go with the majority. Distances are measured with straight-line distance.

The first line of the input contains a single integer n representing the number of known cafés.

The next n lines each contain two floating-point numbers x y followed by a roast word (for example, light, medium, or dark), describing one café’s position and roast.

The next line contains a single integer q representing the number of candidate locations to check.

The last q lines each contain two floating-point numbers x y for the candidate location.

For each candidate location, find the three nearest known cafés, take a majority vote over their roasts, and print the winning roast. If several roasts are tied for the most votes, print the alphabetically smallest roast among them.