Manhattan distance (L1 distance)

Imagine walking in Manhattan. Streets run north-south and east-west, so you move in axis-aligned blocks. The distance between two intersections is the number of blocks you must walk horizontally plus the number of blocks you must walk vertically. You cannot cut diagonally through buildings.

This “city-block” idea defines the Manhattan distance (also called L1 distance or taxicab distance).

For 2D points and , the Manhattan distance between them would be calculated as:

Taxi Blocks

In a grid city, a taxi needs to choose the closest taxi stand using block distance. You know where the stands are and their names. For each pickup location, send the taxi to the nearest stand by Manhattan distance.

The first line of the input contains a single integer n representing the number of taxi stands.

The next n lines each contain two floating-point numbers x y followed by a stand name (one word without spaces), describing one stand’s position and name.

The next line contains a single integer q representing the number of pickup locations.

The last q lines each contain two floating-point numbers x y for a pickup location.

For each pickup location, print the name of the single nearest stand using Manhattan (L1) distance: |x - xi| + |y - yi|. If several stands are exactly tied for the shortest distance, print the one that appears earliest in the input.