Weighted KNN: Closer Voices Are Louder

A city square is running a quick music poll. You already know where some listeners are standing and which genre each one prefers. When a new spot is announced, nearby listeners should count more than distant ones.

You are asked to report the genre at each new spot using distance-weighted voting with straight-line (Euclidean L2) distance:

To do that, you should:

• Find the k closest neighbors

• Calculate the weighted vote for each genre (the sum of all the weights)

• Output the one with the largest weight.

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

The next n lines each contain two floating-point numbers x y followed by a genre word like rock, pop, or jazz, describing one listener’s position and choice.

The next line contains a single integer k representing how many nearest listeners should vote.

The next line contains a single integer q representing the number of spots to evaluate.

The last q lines each contain two floating-point numbers x y for the spot to score.

For each spot, find the genre with the highest weighted votes. If there is a tie by weights, print the alphabetically smallest genre among the tied ones. It's guaranteed that there are no points with 0 distance from the query spot.