배달 시간으로 찾는 매장 위치

작년에 바비큐 명인 코스타가 맨해튼에 식당 여러 곳을 열었다. 처음에는 장사가 잘됐지만, 최근에 문을 연 패스트푸드 체인이 손님을 많이 빼앗아 갔다. 그 체인은 매장에서 음식을 먹을 수 없고 매장 위치도 알려져 있지 않다. 배달만 한다. 코스타는 배달 시간을 근거로 그 체인의 매장이 있을 만한 위치를 알아내려고 한다.

맨해튼의 도로는 좌표축과 평행하다. 그래서 매장과 손님의 위치를 좌표가 모두 정수인 평면 위의 점으로 나타낸다. 점 $(x_1, y_1)$과 점 $(x_2, y_2)$ 사이의 거리는 $|x_2 - x_1| + |y_2 - y_1|$이다.

손님이 온라인으로 주문하면 그 손님과 가장 가까운 매장에서 곧바로 배달이 시작된다. 가장 가까운 매장이 여럿이면 그중 아무 곳에서나 배달한다. 배달 시간은 손님과 그 매장 사이의 거리와 같다.

코스타는 친구 $N$명에게 주문을 넣고 배달 시간을 재 달라고 부탁했다. 모인 자료와 어긋나지 않는 매장 배치를 구하는 프로그램을 작성하시오. 같은 자료에 맞는 배치는 여러 가지일 수 있으므로, 출력은 아래에서 정한 하나의 배치로 고정한다.

첫째 줄에 코스타의 친구 수 $N$이 주어진다.

다음 $N$개의 줄에는 정수 $x$, $y$, $t$가 공백 하나로 구분되어 주어진다. 좌표 $(x, y)$에 있는 친구가 잰 배달 시간이 $t$라는 뜻이다. 친구의 좌표는 모두 서로 다르다.

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

주어진 자료와 어긋나지 않는 매장 배치가 적어도 하나 존재함이 보장된다.

$N$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 친구에게 배달한 매장의 좌표 $x$와 $y$를 공백 하나로 구분해 출력한다.

$i$번째 줄에 쓸 점은 다음 두 조건을 모두 만족하는 정수 좌표의 점 가운데 사전순으로 가장 앞서는 것이다. 사전순은 $x$가 작은 것이 앞서고, $x$가 같으면 $y$가 작은 것이 앞선다.

• $i$번째 친구와의 거리가 정확히 $t_i$이다.
• 모든 친구 $j$에 대해, $j$번째 친구와의 거리가 $t_j$ 이상이다.

이런 점은 항상 존재하고, 그 좌표는 항상 $-10^9$ 이상 $10^9$ 이하이다. 이렇게 고른 $N$개의 점을 모두 모으면 자료와 어긋나지 않는 매장 배치가 된다. 여러 줄에 같은 점이 나올 수 있다.

두 번째 예제를 보자. 친구 2는 $(3, 3)$에 있고 배달 시간이 2이므로, 매장은 $(3, 3)$에서 거리가 정확히 2인 점에 있어야 한다. 후보를 $x$가 작은 순서로 살펴보면 $(1, 3)$, $(2, 2)$, $(2, 4)$, $(3, 1)$, $(3, 5)$는 모두 어떤 친구에게 그 친구의 배달 시간보다 가까워서 매장을 놓을 수 없다. 다음 후보인 $(4, 2)$가 친구 2의 답이다.