Problem Brief

Nearest Neighbouring City

A number of cities are arranged on a simple two by two grid, which is like an ordinary Cartesian plane. Each city is located at an integral (x, y) coordinate intersection. City names and locations are given in the form of a three-part list: [NAME, X, Y] and are provided by the method to solve the problem named findNearestCities, as shown in the pseudocode below. Determine the name of the nearest city that shares either an x or a y coordinate with the queried city. If no other cities share a x or y coordinate, return "NONE". If two cities have the same distance to the queried city (i.e., if candidate cities are at an equal distance to your name [i.e., "your_city" is the closest choice. The distance is the Manhattan distance, the absolute difference in x plus the absolute difference in y.

1Example 1

Input

numOfCities = 3, cities = ["c1", "c2", "c3"], xCoordinates = [3, 2, 1], yCoordinates = [3, 2, 3], numOfQueries = 3, queries = ["c1", "c2", "c3"]

Output

["3", "NONE", "c1"]

Explanation

The three cities at (3, 3), (2, 2), (1, 1) are named c1, c2, and c3 respectively.

For the query "c1", the nearest city sharing an x or y coordinate is "c2" at (2, 2) with a Manhattan distance of 2.

For the query "c2", the nearest city sharing an x or y coordinate is "c3" at (1, 1) with a Manhattan distance of 2.

For the query "c3", the nearest city sharing an x or y coordinate is "c2" at (2, 2) with a Manhattan distance of 2.

2Example 2

Input

numOfCities = 3, cities = ["fastcity", "bigbanana", "xyz"], xCoordinates = [23, 23, 23], yCoordinates = [1, 10, 20], numOfQueries = 3, queries = ["fastcity", "bigbanana", "xyz"]

Output

["bigbanana", "fastcity", "bigbanana"]

Explanation

There are three cities in the input with the corresponding coordinates: 'fastcity' = (23, 1), 'bigbanana' = (23, 10), 'xyz' = (23, 20). The distance between 'fastcity' and 'bigbanana' is 9, 'fastcity' to 'xyz' is 19, and 'bigbanana' to 'xyz' is 10. There are three queries to answer. The first of them asks for the closest city to 'fastcity’, which has exactly one different coordinate. Both 'bigbanana' and 'xyz' have exactly one coordinate that differs from 'fastcity’, but 'bigbanana' is closer and is the correct answer. The second query asks for the closest direct city to 'bigbanana’, and since 'fastcity' is closer than 'xyz’, the correct answer is 'fastcity’. The third query asks for the closest direct city to 'xyz’, and since 'bigbanana' is closer than 'fastcity’, the correct answer is 'bigbanana’.

3Example 3

Input

numOfCities = 3, cities = ["london", "warsaw", "hackerland"], xCoordinates = [1, 10, 20], yCoordinates = [1, 10, 10], numOfQueries = 3, queries = ["london", "warsaw", "hackerland"]

Output

["NONE", "warsaw", "hackerland"]

Explanation

The cities are located as follows: 'london' = (1, 1), 'warsaw' = (10, 10), and 'hackerland' = (20, 10). There are no other cities on a row or column shared with 'london', so the first query returns 'NONE'. The cities of 'warsaw' and 'hackerland' share y values, so they are the closest to each other.

4Example 4

Input

numOfCities = 5, cities = ["green", "red", "blue", "yellow", "pink"], xCoordinates = [100, 200, 300, 400, 500], yCoordinates = [100, 200, 300, 400, 500], numOfQueries = 5, queries = ["green", "red", "blue", "yellow", "pink"]

Output

["NONE", "NONE", "NONE", "NONE", "NONE"]

Explanation

None of the cities share a row or a column, so none meet the criteria for being considered closest to the queried city.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n, m ≤ 10^5

1 ≤ x[i], y[i] ≤ 10^9

1 ≤ length of q[i] and c[i] ≤ 10

Each character of all c[i] and q[i] is in the range ascii[a-z, 0-9, -]

All city name values, c[i], are unique

All cities have unique coordinates