Izhevsk Training Camp

시간 제한3초메모리 제한256 MB

요약

각 대회가 n개 팀의 순위를 제시할 때, 세 대회에서 순서가 모두 같은 팀 쌍의 수가 최소가 되도록 대회 세 개를 고른다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 완전 탐색, 정렬, 조합론
정답자: 아직 제출이 없습니다

문제

Izhevsk Training Camp가 곧 시작된다. 이번 시즌에는 $1$ 부터 $n$ 까지의 연속된 정수로 번호가 붙은 $n$ 개의 팀이 이 행사에 참가한다. 참가 팀에게는 11일 동안 9개의 정교한 대회가 제공된다. 대회는 $1$ 부터 $9$ 까지의 연속된 정수로 번호가 붙는다. 이 중 3개의 대회가 Udmurtia Head Super Cup (UHSC)를 구성한다. 문제는 UHSC에 어떤 세 대회를 고르느냐이다.

Oleg는 Izhevsk Training Camp 개최를 돕는다. 그는 어떤 대회든 각 $n$ 개의 팀이 그 대회에서 몇 등을 할지 미리 안다. 그는 이 지식을 이용해 UHSC의 총 지루함을 최소로 만드는 세 대회를 고르려 한다.

UHSC의 지루함은 세 UHSC 대회 각각에서 팀 $i$ 가 팀 $j$ 를 이긴 팀 쌍 { $i$ , $j$ }의 수로 계산한다.

Oleg가 UHSC의 총 지루함이 가능한 한 최소가 되는 세 대회 $a$ , $b$ , $c$ 를 찾도록 돕는 프로그램을 작성하라.

입력

입력의 첫 줄에는 참가 팀 수 $n$ 이 주어진다 ( $2 \leq n \leq 2^{16}$ ).

다음 9개 줄 중 $i$ 번째 줄에는 $i$ 번째 대회 설명이 주어진다. 각 줄에는 $1$ 부터 $n$ 까지의 서로 다른 양의 정수 $n$ 개가 1등부터 꼴등 순서로 나열된 팀 번호이다.

출력

출력의 유일한 줄에는 UHSC에 고를 대회 번호 세 개 $a$ , $b$ , $c$ 를 출력한다 ( $1 \leq a, b, c \leq 9$ , $a \neq b$ , $a \neq c$ , $b \neq c$ ).

정답이 여러 개면 아무거나 출력한다.

힌트

예시 테스트에서 지루함의 최솟값은 $5$ 이다.

예제1

예제 1

입력

7
1 2 3 4 5 6 7
1 2 4 5 3 7 6
1 3 2 5 7 6 4
1 2 3 4 5 7 6
1 2 3 4 5 6 7
2 1 3 4 5 6 7
7 1 2 3 4 5 6
5 4 1 3 6 7 2
1 2 4 5 3 6 7

예상 출력

3 7 8