Save Christmas!
Santa misplaced a bag of letters but remembers a simple rule: five nearby households in the same neighborhood tend to want similar gifts. He knows where some households are and what each one asked for. For each place he might land, help him guess the gift to save Christmas! Use the five closest known households with the city-block (Manhattan) distance to tell the most probable gift the kids in the household want.

The first line of the input contains a single integer n
representing the number of known households.
The next n
lines each contain two floating-point numbers x y
followed by a single gift word (no spaces), describing one household’s position and gift.
The next line contains a single integer q
representing the number of landing spots to check.
The following q
lines contain two floating-point numbers x y
for Santa’s landing spot.
For each landing spot, predict the most probable gift using the five closest households with the city-block (Manhattan) distance. If there are several equally probable gifts, print the alphabetically smallest one among those. If several households are tied at the cutoff distance when choosing the 5 nearest, keep the ones that appear earlier in the input first.
Input | Output |
---|---|
7 | toys |
6 | blocks |
8 | books |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB