Manhattan Positioning System

Time limit2sMemory limit512 MB

Summary

Given beacons with known grid positions and Manhattan distances to an unknown receiver, decide whether the receiver position is unique, ambiguous, or impossible.

Level: Medium6 of 10
Topics: Geometry, Math, Implementation
Solved: No attempts yet

Problem

The Manhattan Positioning System (MPS) is a variant of GPS built for large cities. MPS treats every position as a lattice point on a regular two dimensional grid, and writes a position as a pair of integers $(X, Y)$ .

To find its own position, an MPS receiver first measures the distance to a number of beacons. Every beacon has a known, fixed position. MPS signals travel along the streets of the city, that is along the $X$ and $Y$ axes only, and never diagonally across a block. A receiver at $(X_R, Y_R)$ that measures the distance to a beacon at $(X_B, Y_B)$ therefore reads the Manhattan distance $|X_R - X_B| + |Y_R - Y_B|$ .

You are given the positions of several beacons and the measured distance from the receiver to each of them. Determine the position of the receiver. The receiver sits on an integer grid point, because MPS does not support fractional coordinates.

Input

The first line contains an integer $N$ , the number of beacons ( $1 \le N \le 1000$ ). Each of the next $N$ lines contains three integers $X_i$ , $Y_i$ , $D_i$ with $-10^6 \le X_i, Y_i \le 10^6$ and $0 \le D_i \le 4 \times 10^6$ . The pair $(X_i, Y_i)$ is the position of beacon $i$ , and $D_i$ is the Manhattan distance between the receiver and beacon $i$ .

No two beacons have the same position.

Output

If exactly one receiver position agrees with the input, print one line with two integers $X_R$ and $Y_R$ , the position of the receiver.

If more than one receiver position agrees with the input, print one line with the word uncertain.

If no receiver position agrees with the input, print one line with the word impossible.

Examples4

Example 1

Input

3
999999 0 1000
999900 950 451
987654 123 13222

Expected output

1000200 799

Example 2
Input
```
2
100 0 101
0 200 199
```
Expected output
```
uncertain
```
Example 3
Input
```
2
100 0 100
0 200 199
```
Expected output
```
impossible
```
Example 4
Input
```
2
0 0 5
10 0 6
```
Expected output
```
impossible
```