GPS on a Flat Earth

On the day aliens finally attacked humanity, nobody could have predicted their choice of weapon. No nuclear weapons, meteors, lasers, or giant monsters. Instead, they subjugated the planet with the power of physics.

The aliens flattened Earth into a two-dimensional surface, which permanently ended our space travel. Humanity survived and resumed daily life as best it could. This two-dimensional world requires changes to many things, including GPS (Global Positioning System).

GPS normally uses radio waves to measure the Euclidean distances from the user to several reference points (satellites), then computes the user's coordinates from those distances. The flat Earth creates two differences that we must adapt to:

• With no satellites in orbit, radio towers must be used instead. Because the surface is flat, each radio tower covers the entire planet.
• Radio waves propagate differently in two dimensions, so the calculation must switch from Euclidean to Manhattan distance. For any two points $(X_1, Y_1)$ and $(X_2, Y_2)$, the Manhattan distance is $|X_1 - X_2| + |Y_1 - Y_2|$.

Your task is to write software for these adapted GPS calculations. Given $N$ reference radio towers and the Manhattan distance from each tower to the user, output all possible user locations. A possible location must be at exactly the measured Manhattan distance from every reference tower. Because the GPS is still in its initial test phase, the user's true location has integer coordinates.

The first line contains an integer $N$ ($1 \le N \le 10^5$), the number of reference radio towers.

Each of the next $N$ lines contains three integers $X$, $Y$, and $D$ ($-10^4 \le X, Y \le 10^4$, $0 \le D \le 4 \times 10^4$). This means the tower at $(X, Y)$ is at Manhattan distance $D$ from the GPS user. No two towers share the same location. The input data is reliable, and the set of possible user locations with integer coordinates is guaranteed to be non-empty and finite.

Output several lines. Each line contains a different pair of integers $X_u$ and $Y_u$, meaning that $(X_u, Y_u)$ is a user location compatible with the input data. Sort the lines by non-decreasing $X_u$, breaking ties by increasing $Y_u$.