Find the nearest city sharing axis

You are given N cities, each with a unique name and integer coordinates (x, y). For any query city, return the nearest city that shares either the same x or the same y coordinate with the query city; distance is the absolute difference along the non-shared coordinate. If there is a tie in distance, break ties by lexicographically smaller city name. Preprocess the cities so that each query can be answered efficiently (e.g., sort by x and by y and use binary search). Specify the data structures, algorithms, and time/space complexity for preprocessing and for each query.