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.

Examples

Input

10 2
1 5
2 5
3 5
4 5
3 10
2 10
6 20
7 20
10 17
100 18

Output

1,5
2,5

1,5
2,5
3,5
4,5

2,15
3,15
1,5
4,5

6,20
7,20
2,15
3,15
1,5
4,5

6,20
7,20
100,18
10,17
2,15
3,15
1,5
4,5