행성 간 여행

최근 바이트 행성계의 우주 교통량이 크게 늘었습니다. 모든 방향으로 자유롭게 움직이는 우주선을 관제하기가 너무 복잡해지자, 의회는 모든 우주선이 (3차원) 좌표축과 평행한 방향으로만 이동하도록 규정했습니다.

이 결정으로 여행업계를 비롯한 여러 분야가 술렁였습니다. 올해 최고 인기 상품은 은하에서 가장 멀리 떨어진 행성으로 떠나는 세상의 끝 여행이 될 예정이었지만, 성간 교통 규칙이 바뀌면서 이제 행성 사이의 거리를 다른 방식으로 계산해야 합니다.

당신은 한 여행사에 고용되어 은하에 있는 모든 행성의 좌표를 받았습니다. 각 행성에 대해, 그 행성에서 가장 먼 행성까지의 거리를 구하세요. 좌표가 $(x_1, y_1, z_1)$, $(x_2, y_2, z_2)$인 두 행성 사이의 거리는 다음과 같이 정의됩니다.

$|x_1 - x_2| + |y_1 - y_2| + |z_1 - z_2|$

첫째 줄에 은하에 있는 행성의 수를 나타내는 정수 $n$ ($1 \le n \le 500\,000$)이 주어집니다. 다음 $n$개의 줄에는 각 행성의 좌표가 세 정수 $x_i$, $y_i$, $z_i$ ($-10^9 \le x_i, y_i, z_i \le 10^9$)로 주어집니다. 같은 좌표가 여러 번 나타날 수 있습니다.

$n$개의 줄을 출력합니다. $i$번째 줄에는 입력의 $i$번째 행성에서 은하에서 가장 먼 행성까지의 거리를 정수로 출력합니다.