The Nearby Recommendation

A librarian works in a large reading room mapped on a 2D grid. They know where some books are and the genre of each one. When a reader stands at a position and asks for a recommendation, the librarian only suggests nearby books (he's a bit lazy, and he doesn't want to reach a far place to grab a book): they look at all books within a cutoff distance D, measure distance with a chosen metric (L1 for Manhattan distance or L2 for straight-line distance), then take the closest k among those nearby books. The recommended genre is the one that appears most among these selected books. If no book is within the cutoff, the librarian's recommendation is unknown.

If several genres are tied for the most votes, print the alphabetically smallest genre. When ordering books by distance to choose the closest k, break equal distances by earlier appearance in the input.

The first line of the input contains a single integer n representing the number of known books. The next n lines each contain two floating-point numbers x y followed by a single-word genre label for that book’s position and genre. The next line contains a word L1 or L2 indicating the distance metric to use. The next line contains an integer k and a floating-point cutoff D. The next line contains a single integer q representing the number of reader positions to check. The last q lines each contain two floating-point numbers x y for a reader’s position.

For each reader position, print the recommended genre based on the rule above, or unknown if no book lies within distance D.