평평한 지구의 GPS

외계인이 마침내 인류를 공격한 날, 아무도 그들이 고른 무기를 예상하지 못했다. 핵무기, 운석, 레이저, 거대 괴수는 없었다. 대신 외계인은 물리 법칙의 힘으로 지구를 굴복시켰다.

외계인은 지구를 2차원 평면으로 바꾸었고, 인류는 우주 비행 능력을 영원히 잃었다. 인류는 살아남아 할 수 있는 만큼 일상을 다시 이어 갔다. 이 2차원 세상에서는 GPS(Global Positioning System)를 포함한 많은 것을 조정해야 한다.

GPS는 보통 전파를 이용해 사용자에서 여러 기준점(위성)까지의 유클리드 거리를 재고, 이 거리로 사용자의 좌표를 계산한다. 하지만 평평해진 지구에는 맞춰야 할 두 가지 차이가 있다.

• 궤도에 위성이 없으므로 대신 무선 탑을 써야 한다. 표면이 평면이므로 각 무선 탑이 지구 전체를 커버한다.
• 2차원에서는 전파가 다르게 전파되므로, 계산에 쓰는 거리를 유클리드 거리에서 맨해튼 거리로 바꿔야 한다. 두 점 $(X_1, Y_1)$과 $(X_2, Y_2)$ 사이의 맨해튼 거리는 $|X_1 - X_2| + |Y_1 - Y_2|$이다.

여러분의 과제는 이렇게 수정된 GPS 계산을 수행하는 소프트웨어를 작성하는 것이다. N개의 기준 무선 탑과 각 탑에서 사용자까지의 맨해튼 거리가 주어지면, 가능한 사용자 위치를 모두 출력해야 한다. 가능한 위치는 모든 기준 무선 탑에서 측정된 맨해튼 거리와 정확히 일치해야 한다. GPS는 아직 시험 단계이므로 사용자의 실제 위치는 정수 좌표다.

첫 줄에 기준 무선 탑의 개수를 나타내는 정수 $N$($1 \le N \le 10^5$)이 주어진다.

이어지는 $N$개의 줄에는 각각 세 정수 $X$, $Y$, $D$($-10^4 \le X, Y \le 10^4$, $0 \le D \le 4 \times 10^4$)가 주어진다. 이는 좌표 $(X, Y)$에 있는 탑이 사용자로부터 맨해튼 거리 $D$만큼 떨어져 있다는 뜻이다. 두 탑이 같은 위치에 있는 경우는 없다. 입력 데이터는 신뢰할 수 있으며, 정수 좌표를 가진 사용자의 가능한 위치 집합이 공집합이 아니고 유한하다고 보장된다.

여러 줄을 출력한다. 각 줄에는 서로 다른 정수 쌍 $X_u$, $Y_u$를 출력하며, 이는 $(X_u, Y_u)$가 입력 데이터와 맞는 사용자 위치라는 뜻이다. 줄은 $X_u$가 작은 순서로 정렬하고, $X_u$가 같으면 $Y_u$가 작은 순서로 정렬한다.