31634번 - 가지 소환 마법

문제

한국가지협회는 질 좋은 가지를 저렴한 가격에 공급하기 위해 다방면으로 연구하고 있습니다. 가지 소환 마법은 최근에 개발된 방법으로, 적은 수의 가지를 제물로 바쳐 수많은 가지를 소환하는 마법입니다.

가지 소환 마법을 사용하기 위해서는 $N$개의 가지를 공중에 띄우고 주문을 외워야 합니다. 가지의 위치를 3차원 좌표공간 위 점으로 나타냈을 때, 각 점에 적당한 함수 $f(P)$를 찾아 적용합니다. 함수 $f(P)$는 다음 조건을 만족시켜야 합니다.

• $f(P)$의 정의역과 공역은 각 좌표의 값이 유리수인 모든 점 $(x, y, z)$의 집합입니다.
• 어떤 서로 다른 두 점 $A,ドル $B$를 고르더라도 $f(A)$와 $f(B)$는 다릅니다.
• 서로 다른 세 점 $A,ドル $B,ドル $C$가 한 직선 위에 있는 것과, $f(A),ドル $f(B),ドル $f(C)$가 한 직선 위에 있는 것은 동치입니다.
• 서로 다른 두 점 $A,ドル $B$와 서로 다른 두 점 $C,ドル $D$에 대해서 직선 $\overleftrightarrow{AB}$와 직선 $\overleftrightarrow{CD}$가 평행한 것은 직선 $\overleftrightarrow{f(A)f(B)}$와 직선 $\overleftrightarrow{f(C)f(D)}$가 평행한 것과 동치입니다. $\overleftrightarrow{AB} = \overleftrightarrow{CD}$이면 직선 $\overleftrightarrow{AB}$와 직선 $\overleftrightarrow{CD}$는 평행합니다.

$N$개의 점에 모두 $f(P)$를 적용한 뒤에, $M$개의 각 점을 꼭짓점으로 하는 다각형이 정$M$각형이 되도록 $N$개의 점 중 적당한 $M$개의 점을 선택하면 $N \times M$개의 가지를 소환할 수 있습니다. $(M \ge 3)$ 단, 적당한 $f(P)$를 찾지 못하거나 적당한 $M$개의 점을 선택하지 못한다면 소환이 실패합니다. $N$개의 가지의 위치를 나타내는 점이 주어질 때, 적절한 함수 $f(P)$와 $M$개의 점을 단 한 번 선택하여 최대 몇 개의 가지를 소환할 수 있는지 알아내 봅시다.

입력

첫 번째 줄에 가지의 수 $N$이 주어집니다. $(3 \le N \le 500)$

다음 $N$개 줄 각각에 가지의 위치를 나타내는 점의 좌표가 주어집니다. 그중 $i$번째 줄에는 $i$번째 가지의 위치를 나타내는 점의 좌표 $(x_i, y_i, z_i)$를 나타내는 정수 $x_i,ドル $y_i,ドル $z_i$가 공백으로 구분되어 주어집니다. $(0 \le x_i, y_i, z_i \le 10^8)$

모든 가지의 위치는 다릅니다.

출력

첫 번째 줄에 적당한 함수 $f(P)$와 적당한 $M$개의 점을 단 한 번 선택하여 최대 몇 개의 가지를 소환할 수 있는지 출력합니다.

제한

힌트