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, with a empty line after each table:

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

Some code

You may want to use this Team class. But you do not have to.

public class Team implements Comparable<Team> {
    public int score;
    public int id;
        
    public Team(int i, int s) {
        id = i; score = s;
    }

    @Override
    public int compareTo(Team a) {
        if(score < a.score) {
            return -1;
        } else if(score > a.score) {
            return 1;
        } else {
            return id - a.id;
        }
    }    
}