Proximity Routing Commands

You are given a list of text commands commands that operate a registry of named regions, each at an integer latitude and longitude with a capacity. Process the commands in order. Return one output line per command.

Commands

REGISTER <name> <lat> <lon> <capacity>: add a region. The output is OK, or ERROR (with no change made) if any rule fails:

• lat must be in [-90, 90] and lon in [-180, 180].
• capacity must be greater than 0.
• name must not already be registered.

A newly registered region is healthy and has capacity units of remaining capacity.

SET_HEALTHZ <name> <true|false>: mark a registered region healthy or unhealthy. The output is OK, or ERROR if the name is not registered.

DISTANCE <lat1> <lon1> <lat2> <lon2>: the output is the great-circle distance in kilometres between the two points, computed with the Haversine formula below and rounded half-up to an integer. These arguments are not range-checked.

ROUTE <lat> <lon>: route a request. The output is ERROR if lat or lon is outside the ranges above. Otherwise:

• The candidates are all healthy regions, in the order they were registered.
• The chosen region is the candidate with remaining capacity greater than 0 whose rounded distance to the request is smallest. Among equal rounded distances, the earliest-registered wins.
• If a region is chosen, its remaining capacity decreases by 1 and the output is <name> <distance> <candidates...>: the rounded distance, then every candidate name, all separated by single spaces.
• Otherwise the output is NONE 0 <candidates...> (just NONE 0 when there are no candidates).

Haversine distance

With R = 6371 km and angles converted to radians:

a = sin²((lat2 - lat1) / 2) + cos(lat1) · cos(lat2) · sin²((lon2 - lon1) / 2)
c = 2 · atan2(√a, √(1 - a))
d = R · c

Every distance in the tests is at least 10^-6 km away from a .5 boundary, so rounding is unambiguous.

Examples

Example 1

Input: commands = ["REGISTER us-east-1 38 120 100", "REGISTER us-west-2 50 112 30", "SET_HEALTHZ us-west-2 false", "REGISTER eu-east-1 -10 15 0"]
Output: ["OK", "OK", "OK", "ERROR"]
Explanation: The last registration fails because its capacity is 0.

Example 2

Input: commands = ["DISTANCE 40 -74 51 0", "DISTANCE 0 0 0 1"]
Output: ["5645", "111"]
Explanation: 5645.48 km rounds to 5645; one degree of longitude on the equator is 111.19 km.

Example 3

Input: commands = ["REGISTER us-east-1 0 0 1", "REGISTER ap-south-1 0 0 1", "ROUTE 0 0", "SET_HEALTHZ ap-south-1 false", "ROUTE 0 0"]
Output: ["OK", "OK", "us-east-1 0 us-east-1 ap-south-1", "OK", "NONE 0 us-east-1"]
Explanation: Both regions are 0 km away; us-east-1 was registered first, so it is chosen and its only unit of capacity is consumed. The second ROUTE finds us-east-1 healthy (so it is still a candidate) but out of capacity, and ap-south-1 unhealthy, so nothing can be chosen.