Friendship is a number

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 32M

Problem type

Griffy now needs to make friends at Don Mills! Griffy has found N programmer candidates that he may want to make friends with. The IDs of the programmers are labelled 1, 2, \dots, N. Each programmer has T different traits, and their total friend-points is the product of all of these traits. Griffy wants to find the top 3 candidates with the most friend-points, and make friends with them! Griffy is not very good at math, so please help him! It is guaranteed that there will be no ties.

Input Specification

First line: A single integer N (3 \le N \le 100).

Lines 2 to N+1: an integer, T, followed by T space separated integers, representing the candidate's traits (1 \le T \le 100, for each trait t, -10 \le t \le 10).

It is guaranteed that the friend-points will fit into a 64-bit signed integer.

Output Specification

3 lines, the IDs of the top three candidates sorted in decreasing order of friend-points.

Sample Input

3 2 5 1
2 5 3
3 -2 6 4
4 1 1 1 1
2 10 10

Sample Output


Explanation for Sample Output

Candidate 5 has 10 \times 10 = 100 friend-points, candidate 2 has 5 \times 3 = 15 friend-points, and candidate 1 has 10 friend-points. These are the top 3 friend-points values.


There are no comments at the moment.