Eurokulen

Interview

Time limit1sMemory limit1024 MB

Summary

Given each farm's ranking of the other kulen, find the top three by points, then again after erasing the votes of farms that exchanged equal points with another farm.

Level: Easy3 of 10
Topics: Array, Sorting, Implementation
Solved: No attempts yet

Problem

There are $N$ small family farms (OPG) labeled from 1 to $N$ taking part in the vote for the best kulen in Europe. After the presentation and tasting, voting begins. Each OPG ranks the other $N-1$ OPGs. It gives $N-1$ points to the kulen it likes best, $N-2$ points to the next one, and so on, down to 1 point for the last one.

Question 1: Print the labels of the OPGs whose kulen took first, second, and third place. If several kulen have the same number of points, the one with the smaller label ranks higher.

However, the European kulen commissioner K.M. from Zagreb checks the result more closely. Europe dislikes it when two OPGs exchange points, that is, when OPG A gives X points to OPG B and OPG B gives X points to OPG A. When the commissioner finds such a case, the votes of A and B are erased and do not count when the new ranking is determined. Their kulen stay on the list. Only their votes are deleted.

Question 2: Print the labels of the OPGs whose kulen took first, second, and third place after the points of the OPGs that exchanged points are erased. If several kulen have the same number of points, the one with the smaller label ranks higher.

Input

The first line contains a natural number $N$ ( $3 \le N \le 1000$ ). Of the next $N$ lines, the $i$ -th line contains $N-1$ natural numbers $K_j$ ( $1 \le K_j \le N-1$ , $K_j \ne i$ ), the labels of the kulen in the order that OPG $i$ ranked them.

Output

Print the three labels asked for in Question 1 on the first line. Print the three labels asked for in Question 2 on the second line.

Hint

Explanation of the first test case: OPG 1 earned two points, OPG 2 earned three points, and OPG 3 earned four points. OPG 1 gave OPG 2 one point, and OPG 2 gave OPG 1 one point too. Likewise, OPG 2 gave OPG 3 two points, and OPG 3 gave OPG 2 two points. Erasing all points given by the three OPGs leaves every OPG with zero points, so the tie-break by label gives the order 1, 2, 3.

Examples3

Example 1
Input
```
3
3 2
3 1
2 1
```
Expected output
```
3 2 1
1 2 3
```
Example 2
Input
```
4
2 3 4
3 4 1
2 4 1
2 1 3
```
Expected output
```
2 3 4
2 3 1
```

Example 3

Input

Expected output

4 5 1
1 4 5