빈 직육면체

다음 조건을 모두 만족하는 직육면체를 정규 직육면체라고 하자.

• 꼭짓점 중 하나가 원점 $(0, 0, 0)$에 있다.
• 그 꼭짓점에서 뻗어 나가는 세 모서리가 각각 $x$축, $y$축, $z$축의 양의 반직선 위에 놓인다.
• 각 모서리의 길이는 $10^6$ 이하이다.

따라서 정규 직육면체는 원점의 반대쪽 꼭짓점 $(x, y, z)$ 하나로 완전히 결정되며, $1 \le x, y, z \le 10^6$ 이고 공간에서 $[0, x] \times [0, y] \times [0, z]$ 영역을 차지한다. 그 부피는 $x \cdot y \cdot z$ 이다.

좌표가 모두 $[1, 10^6]$ 범위의 정수인 점들의 집합 $A$가 주어진다. 어떤 점이 직육면체 안에 있다는 것은 그 점이 직육면체의 내부(경계면 위가 아니라 엄밀한 내부)에 있다는 뜻이다. 즉, 점 $(a, b, c)$가 직육면체 $(x, y, z)$의 내부에 있으려면 $a < x$, $b < y$, $c < z$를 모두 만족해야 한다.

$A$의 어떤 점도 내부에 포함하지 않는 정규 직육면체의 최대 부피를 구하라. 같은 최대 부피를 갖는 직육면체가 여러 개일 수 있으나, 부피 값 자체만 출력하면 된다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 집합 $A$의 점 좌표를 읽는다.
• 내부에 $A$의 점을 하나도 포함하지 않는 정규 직육면체의 최대 부피를 구한다.
• 그 부피를 표준 출력에 쓴다.

첫째 줄에 집합 $A$의 점의 개수를 나타내는 음이 아닌 정수 $n$ ($0 \le n \le 5000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 한 점의 좌표를 나타내는 세 정수 $x$, $y$, $z$ ($1 \le x, y, z \le 10^6$)가 하나의 공백으로 구분되어 주어진다.

정규 직육면체의 내부가 주어진 점을 하나도 포함하지 않을 때의 최대 부피를 정수 하나로 출력한다. $A$가 비어 있으면 답은 $10^6 \cdot 10^6 \cdot 10^6 = 10^{18}$ 이다.