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.

santa.jpg

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
0 0 toys
2 0 books
0 2 books
3 3 games
1 1 toys
-1 2 books
2 1 toys
2
1 0
2 2

toys
books

6
0 0 dolls
0 1 blocks
1 0 blocks
1 1 trains
2 0 blocks
0 2 dolls
2
0.9 0.9
0 2

blocks
blocks

8
-1 0 candy
1 0 candy
0 -1 books
0 1 books
2 0 games
0 2 games
-2 0 candy
0 -2 books
1
0 0

books

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue