Hide

Problem M
Triangle Drama

It’s the year 3035, and you are Chief Relationship Officer on the Pluto colonization mission, currently en route to the beigeish not-planet. Your task is to make sure that there is no excessive amount of relationship drama during the 10 year long trip. The biggest source of issues are the so-called triangle dramas. These are formed when three single people have a pairwise quite high potential for starting a relationship. If two people in a triangle drama starts a relationship, the tension created with the third person may be an obstacle to the mission1.

The ship’s relationship AI used to analyze the potential for triangle drama on the ship continuously for you, until it broke down after its partner, the navigation system, had an affair with life-support. Until it has watched enough romcoms to be ready to “get back out there”, you’ll have to perform this analysis yourself.

If three people have pairwise relationship potential $a$, $b$ and $c$, their potential for drama is $abc$. Write a program to find the three singles with the highest potential for drama, given the relationship potential of all couples on the ship.

Input

The first line contains an integer $N$ ($3 \le N \le 100$), the number of singles on the mission.

The next $N$ lines describe the relationship potentials of everyone on the ship. Each line contains $N$ integers between $0$ and $100$, the relationship potential in percent. The $j$’th number on the $i$’th line describes the relationship potential between people $i$ and $j$.

The relationship potential is symmetric, and a person always has relationship potential $0$ with themselves (narcissism is filtered out during the pre-mission psychological evaluation).

Output

Output three integers – the indices of the people with the highest potential for drama in increasing order. If there are several triangle dramas $(a, b, c)$ with the same potential for drama, choose first the one with the smallest $a$, and if tied, the smallest $b$, and if still tied, the smallest $c$..

Sample Input 1 Sample Output 1
4
0 1 0 0
1 0 2 4
0 2 0 3
0 4 3 0
2 3 4
Sample Input 2 Sample Output 2
4
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0
1 2 4

Footnotes

  1. For example, jealousy might cause them to accidentally eject the two lovebirds off the ship.

Please log in to submit a solution to this problem

Log in