Fence Sitters

Two music fan clubs recruit in a park. You know where some existing fans are standing and which club they cheer for: each is a point on a 2D map with a club name. When a new person stands somewhere, they ask which club the two closest nearby fans would vote for. If those two closest fans disagree, it is a tie.

The first line of the input contains a single word metric that is either L2 for straight-line distance or L1 for Manhattan distance. The second line contains a single integer n representing the number of known fans. The next n lines each contain two floating-point numbers x y followed by a club name (a single word), describing one fan’s position and club. The next line contains a single integer q representing the number of standing positions to check. The last q lines each contain two floating-point numbers x y for the new person’s position.

For each position, compute distances to all known fans using the indicated metric, take the two nearest fans (k=2), and print the winning club if both belong to the same club; otherwise, print tie. When distances are exactly equal during neighbor selection, treat earlier lines in the input as closer.