DOTAA2 - HELP NERUBAN

Neruban, the DotA gamer knows to play with some heroes. You are given the list of heroes that Neruban knows to play with. You are also given how accurate he can play, how fast he can play and how stupidly he can play with every hero. i.e. for each hero you are given 3 values Accuracy (a), Speed (v) and Stupidity (s). Neruban wants to rank the heroes according to the order with which he can play perfectly. So sort the heroes based on higher accuracy, higher speed and lower stupidity.

For example a hero with a = 10, v = 1, s = 100 is higher ranked than a hero with a = 1, v = 100, s = 0, because first preference is given for the accuracy of the hero.

Similarly a hero with a = 10, v = 5, s = 20 is higher ranked than a hero with a = 10, v = 4, s = 40, because second preference is given for the speed of the hero.

A hero with a = 10, v = 3, s = 10 is higher ranked than a hero with a = 10, v = 3, s = 15, because stupidity of a player should be lower

If any two heroes have same accuracy, speed and stupidity, sort them based on their name alphabetically.

Input

The first line consists of an integer n, the number of heroes. The next n lines describe each hero with 4 values - the name of the hero, accuracy, speed and stupidity.

Output

Sort the heroes based on the above criteria and print the rank list.

Constraints

1 <= n <= 100000
Name of a hero <= 15 characters (all lower case)
0 <= a, v, s <= 100

Example

Input:
4
goblinshredder 45 66 98
pudge 45 86 76
shadowfiend 99 98 2
invoker 45 86 75
 
Output:
shadowfiend
invoker
pudge
goblinshredder

Added by:cegprakash
Date:2012-10-12
Time limit:1.364s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2022-09-13 00:02:34
<snip>
runtime????
[Simes]: use the forum for if you want help.

Last edit: 2022-09-13 08:53:35
2021-06-21 09:47:02
Don't use pair of pair,pair. It will cause runtime error instead use struct.
2020-10-21 13:18:24
thanks @dunjen_master
2017-08-18 21:28:28
AC in 3 goes.....dont forget to check the case where every parameter is same and then u have to compare the two strings...i got 2 WA due to this


Last edit: 2017-08-18 21:28:44
2017-05-28 15:34:58
@Abhinav , Mine got accepted , don't think there are any tricky test cases , just make sure your compare function is correct , there are many if-else branches to be made and even smallest of mistakes can show WA.
Hint:Return a value from the compare function for every possible comparison between two players.
2015-01-20 18:10:29 Abhinav
getting WA, any tricky case ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.