Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Issue'r Desh

Limits 1s, 512 MB

People can be so hype-driven sometimes. One moment they are talking about something serious, an accident for example, and in a way as if they are the victims themselves (which is good). But the very next day they will talk about something nonsense forgetting the seriousness of the previous topic. Rather than solving the issues, it is as-if people are always just looking for new issues to talk about.

In this problem, you have to work with some such issues. But the fact is, you don’t want to focus on anything nonsense like the others. You’ll use your brain and your most valuable humor. You’ll be given an issue along with a factor indicating how important it is and you have to keep track of the most important issue of the day.

For example, if an issue X occurs on the 1st day having the importance factor 5 and if an issue Y occurs on the 2nd day, and it has the importance factor 2, then the issue for the 1st and the 2nd days will be X.

If two issues have the same importance factor, the new one will be picked.

Input

The first line of the input will contain N and M (1 ≤ N, M ≤ 100), the number of issues and the total number of days.

The next N lines will each contain S (1 ≤ Length of S ≤ 100) and R (R ≤ 100), where S is the issue name and R is the importance factor of the issue. The string S will contain only lowercase and uppercase alphabets.

Output

For each day from 1 to M, you have to print the name of the most important issue on that day.

Samples

InputOutput
3 3
BDvsEngTtwenty 3
ChokbazarTragedy 5
JanlaDiaBairHoiaFankhaDiaNamiGesi 2
Day 1: BDvsEngTtwenty
Day 2: ChokbazarTragedy
Day 3: ChokbazarTragedy

Discussion