Izhevsk Training Camp

Time limit3sMemory limit256 MB

Summary

Given nine contests, each a ranking of n teams, pick three contests so that the number of team pairs ordered the same way in all three is minimized.

Level: Hard8 of 10
Topics: Bit manipulation, Brute force, Sorting, Combinatorics
Solved: No attempts yet

Problem

The Izhevsk Training Camp is about to begin. This season, $n$ teams numbered with consecutive integers from $1$ to $n$ will take part in the event. Nine contests will be offered to the participating teams over a period of eleven days. The contests are numbered with consecutive integers from $1$ to $9$ . Three of these contests will form the Udmurtia Head Super Cup (UHSC). The question is: which three contests should be chosen for the UHSC?

Oleg helps run the Izhevsk Training Camp. For any contest, he knows in advance what place each of the $n$ teams will take. He wants to use this knowledge to select three contests so that the total boredom of the UHSC is minimized.

The boredom of the UHSC is the number of pairs of teams { $i$ , $j$ } such that team $i$ beat team $j$ in each of the three UHSC contests.

Write a program that helps Oleg find three contests $a$ , $b$ , and $c$ for the UHSC such that the total boredom of the UHSC is as small as possible.

Input

The first line of the input contains an integer $n$ , the number of participating teams ( $2 \leq n \leq 2^{16}$ ).

The $i$ -th of the following nine lines contains the description of the $i$ -th contest: $n$ distinct positive integers from $1$ to $n$ , the team numbers ordered from first place to last.

Output

The only line of the output should contain three positive integers $a$ , $b$ , and $c$ , the numbers of the contests chosen for the UHSC ( $1 \leq a, b, c \leq 9$ , $a \neq b$ , $a \neq c$ , $b \neq c$ ).

If there are several correct answers, output any of them.

Hint

For the sample test, the minimum possible value of boredom is $5$ .

Examples1

Example 1

Input

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

Expected output

3 7 8