Hide

Problem G
Manhattan Positioning System

The Manhattan Positioning System (MPS) is a modern variant of GPS, optimized for use in large cities. MPS assumes all positions are discrete points on a regular two-dimensional grid. Within MPS, a position is represented by a pair of integers $(X,Y)$.

To determine its position, an MPS receiver first measures its distance to a number of beacons. Beacons have known, fixed locations. MPS signals propagate only along the $X$ and $Y$ axes through the streets of the city, not diagonally through building blocks. When an MPS receiver at $(X_ R,Y_ R)$ measures its distance to a beacon at $(X_ B,Y_ B)$, it thus obtains the Manhattan distance: $|X_ R - X_ B|+|Y_ R - Y_ B|$.

Given the positions of a number of beacons and the Manhattan-distances between the receiver and each beacon, determine the position of the receiver. Note that the receiver must be at an integer grid position (MPS does not yet support fractional coordinates).

Input

The first line contains an integer $N$, the number of beacons ($1 \leq N \leq 1000$). Then follow $N$ lines, each containing three integers, $X_ i$, $Y_ i$, and $D_ i$, such that $-10^6 \leq X_ i, Y_ i \leq 10^6$ and $0 \leq D_ i \leq 4 \cdot 10^6$. The pair $(X_ i, Y_ i)$ denotes the position of beacon $i$, while $D_ i$ is the Manhattan distance between receiver and beacon $i$.

No two beacons have the same position.

Output

If there is exactly one receiver position consistent with the input, write one line with two integers, $X_ R$ and $Y_ R$, the position of the receiver.

If multiple receiver positions are consistent with the input, write one line with the word “uncertain”.

If no receiver position is consistent with the input, write one line with the word “impossible”.

Sample Input 1 Sample Output 1
3
999999 0 1000
999900 950 451
987654 123 13222
1000200 799
Sample Input 2 Sample Output 2
2
100 0 101
0 200 199
uncertain
Sample Input 3 Sample Output 3
2
100 0 100
0 200 199
impossible
Sample Input 4 Sample Output 4
2
0 0 5
10 0 6
impossible

Please log in to submit a solution to this problem

Log in