N radiobeacons are located on the plane. Their exact positions are unknown but we know that N ≤ 10 and that their coordinates are integers from 1 to 200. Each beacon produces unique signal, that distinguishes it from the other beacons.
In some different places, we should call them checkpoints, coordinates of which are well known, there were conducted measurements. As a result of these measurements distances from checkpoints to some of beacons became known. Here we should note, that the distance between points A and B equals max(|Ax − Bx|, |Ay − By|).
You need to get positions of all beacons basing on coordinates of the checkpoints and results of measurements, if that is possible.
First line contains an integer M, the number of checkpoints. 1 ≤ M ≤ 20. Then M lines follow, each of them contains an information received from one of the checkpoints, formatted as follows:
where Xi, Yi are coordinates of checkpoints, IDk is ID of beacon k, Rk is a distance from checkpoint i to beacon k. Coordinates of checkpoints are integers from 1 to 200. Each checkpoint measures at least one signal. IDs of beacons are integers from 1 to 30000.
Output should consist of N lines describing positions of the beacons.
If there is exactly one position (xk, yk) of the k'th beacon satisfying the results of measurements and such that
1 ≤ xk, yk ≤ 200, you should output
in the k'th line (IDk is ID of the k'th beacon).
In the other case you should output <IDk>:UNKNOWN in the k'th line. All lines should be ordered by IDk in an ascending order.
It is guaranteed that measurements are consistent, i.e. the solution always exists, but may be ambiguous.
Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Round