Student Average Scores Ranking

You are given the information of n students. Each student record consists of the student's name followed by three integer scores. The average score is computed as \(\frac{s_1 + s_2 + s_3}{3}\). Your task is to sort the students in descending order based on their average score. In the event of a tie (i.e. equal average scores), sort the names in ascending alphabetical order.

If the input is empty or any student's data does not consist of exactly one name and three scores, output Invalid input.

Note: The input is provided via standard input and the output should be printed via standard output.

inputFormat

The input is read from stdin in the following format:

n
name1 score1 score2 score3
name2 score1 score2 score3
... 

Here, n (an integer greater than 0) denotes the number of students. Each of the next n lines contains a student's name and three integer scores separated by spaces.

outputFormat

If the input is invalid (i.e. n is 0 or any record does not contain exactly four fields), output:

Invalid input

Otherwise, output the student names sorted as specified—all on one line and separated by a single space. The average score is calculated as \(\frac{s_1 + s_2 + s_3}{3}\).

## sample

5
John 88 77 93
Alice 85 90 92
Bob 78 81 79
Jane 92 85 88
Emma 88 84 90

Alice Jane Emma John Bob