Restaurant Locations from Delivery Times

Last year Kosta, a barbecue master, opened several restaurants in Manhattan. Business was good at first, but a fast food chain that opened recently took away many of his customers. That chain has no place to eat in and nobody knows where its restaurants are. It only delivers. Kosta wants to work out where those restaurants can be, using the delivery times.

The streets of Manhattan run parallel to the coordinate axes. Every restaurant and every customer therefore sits on a point of the plane with integer coordinates. The distance between $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_2 - x_1| + |y_2 - y_1|$.

When a customer orders online, delivery starts at once from the restaurant closest to that customer. If several restaurants are equally close, the food comes from any one of them. The delivery time equals the distance from the customer to that restaurant.

Kosta asked $N$ friends to order food and measure the delivery time. Write a program that finds a layout of restaurants consistent with the collected data. Several layouts can fit the same data, so the output is fixed to the single layout described below.

The first line contains the integer $N$, the number of Kosta's friends.

Each of the next $N$ lines contains three integers $x$, $y$ and $t$ separated by a single space. The friend at $(x, y)$ measured delivery time $t$. All friends sit on different coordinates.

$1 \le N \le 1000$, $-10^8 \le x, y \le 10^8$, $0 \le t \le 10^8$.

At least one layout of restaurants consistent with the given data exists.

Print $N$ lines. Line $i$ contains the coordinates $x$ and $y$ of the restaurant that delivered to friend $i$, separated by a single space.

The point on line $i$ is the lexicographically smallest point with integer coordinates that satisfies both conditions below. In lexicographic order a smaller $x$ comes first, and among equal $x$ a smaller $y$ comes first.

• Its distance to friend $i$ is exactly $t_i$.
• Its distance to friend $j$ is at least $t_j$ for every friend $j$.

Such a point always exists, and its coordinates are always between $-10^9$ and $10^9$. The $N$ chosen points taken together form a layout consistent with the data. The same point can appear on several lines.

Take the second sample. Friend 2 sits at $(3, 3)$ and measured a delivery time of 2, so the restaurant must be at distance exactly 2 from $(3, 3)$. Going through the candidates by increasing $x$, the points $(1, 3)$, $(2, 2)$, $(2, 4)$, $(3, 1)$ and $(3, 5)$ each lie closer to some friend than that friend's own delivery time, so no restaurant can be placed there. The next candidate is $(4, 2)$, and that is the answer for friend 2.