Arun is a good Badminton Player. He has huge female fan Following . he has to make sure they are all happy and rooting for him to win the gold medals. but due to lack of time He can meed only atmost T. Each of his Fan is Defined by two parameters : Name and Fan Quotient. The name defines the name of the fan, while the fan quotient is a measure of the fan's devotion towards Arun. Higher the fan quotient, greater is the devotion. Arun now wants to meet T of his fans. While selecting the fans he wants to meet, he wants to make sure that a fan with a higher fan quotient should be given a chance in favour of those with lesser fan quotient. In case of ties, he sorts their name lexicographically and chooses the lexicographically lesser named fan.Given details of N fans, can you help out Arun by giving him a list of fans he would be interacting with?

Input The first line contains N and T, the number of fans and the maximum number of fans Arun can meet. Each of the next N lines contains a string and an integer separated by a space. The string denotes the name of the fan while the integer depicts the fan quotient.

Output Output T lines, each containing the name of the fans selected. Fans with higher fan quotient should be outputted first and in case of a tie, the lexicographically minimum name should come first.

Constraints
1<=T<=N<=1000<
1<=lengthofname<=20
1<=fanquotient<=109

Note :Name would only consist of characters in set [a-z]. It is not guaranteed that the names are distinct.