Description

小学乒乓球比赛，因为想达到以赛代练的目的，经常采用循环赛。比赛的规则是胜者得3分，和者得1分，败者不得分。最后根据得分进行排名。

Input

若干场赛事，每场赛事为一组数据，每组数据开始为一个整数n(<50)，表示参赛人数（如果n为0则处理结束），后跟n(n-1)/2行比赛结果。每行比赛结果为A、B、f构成，A和B为参赛人名，f为结果，f为1表示A胜B，为0表示A与B和。总是将胜者排前，所以不存在A败于B的情况。

Output

每场赛事之间有一个空行，一场赛事中按名次在各行输出，名次与名字之间以：和空格间隔，并列名次的名字在同一行输出，按字典序以空格隔开。

Sample

Input

3
Jone Jack 1
Jone Smith 1
Smith Jack 0
0

Output

1: Jone
2: Jack Smith