Request Routing System

Process commands in order to maintain data center registrations, health status, and current load; support great-circle distance queries, and route each request to the nearest healthy data center that still has capacity. Distances use the Haversine formula with an Earth radius of 6371 km. Output and routing order use the distance rounded to an integer number of kilometers, with ties broken by name in ascending order.

输入格式

The first line contains q (0..5000), followed by q lines of commands; at most 200 data centers are registered in total. Coordinates are finite decimals, with latitude in [-90,90], longitude in [-180,180], and at most 18 decimal places. Commands are REGISTER name latitude longitude capacity, SET_HEALTHY name true|false, DISTANCE lat1 lon1 lat2 lon2, or ROUTE latitude longitude. capacity is a positive integer; name consists of 1..32 ASCII letters, digits, underscores, or hyphens. Command names and argument counts are valid; invalid values return ERROR as the statement specifies.

输出格式

Output one line per command. REGISTER/SET_HEALTHY outputs OK or ERROR; DISTANCE outputs an integer number of kilometers or ERROR; ROUTE outputs name distance candidates, or None candidates if every healthy data center is full. candidates is the comma-separated list of names of all healthy data centers sorted by (rounded integer kilometers, name); output None when there is no healthy data center.

样例 1

输入：

7
REGISTER us-west 38 -122 100
REGISTER us-east 41 -74 150
REGISTER us-west 50 -100 50
REGISTER invalid-node 91 0 100
REGISTER invalid-cap 0 0 0
SET_HEALTHY us-east false
SET_HEALTHY fake-node true

输出：

OK
OK
ERROR
ERROR
ERROR
OK
ERROR

样例 2

输入：

3
DISTANCE 38 -122 41 -74
DISTANCE 0 0 0 0
DISTANCE 91 0 0 0

输出：

4080
0
ERROR

样例 3

输入：

7
REGISTER node-A 0 0 1
REGISTER node-B 0 0 1
REGISTER node-C 10 10 100
SET_HEALTHY node-C false
ROUTE 0 0
ROUTE 0 0
ROUTE 0 0

输出：

OK
OK
OK
OK
node-A 0 node-A,node-B
node-B 0 node-A,node-B
None node-A,node-B

样例说明

This site restricts input values to finite decimals with at most 18 decimal places. On this input domain, the exact spherical distance is never exactly a half-integer number of kilometers, so the nearest-integer result is unique; the reference implementation rounds halves up to avoid differences in how language libraries handle exact ties.