01204212/homework/top scores

This is part of 01204212

You want to maintain a table of teams with top 10 scores in a world-wide game competition. You will get M updates. After every K updates, you want to print out a table of teams with top 10 scores. If there are ties, you should show teams with smaller IDs first.

Input/output

Input

First line: two integers M and K Next M lines: two integers t and s, where t is the team ID (1<=t<=100,000) and s is the additional scores. Initially every team has score of 0.

Output

After every K updates, you should print out a table with top 10 scores in the following format:

teamID,score
teamID,score
teamID,score
...

If there are less than 10 teams, output all of them.