Description

自从实施了集星卡换奶茶的奖励措施以后，每次考试的成绩就变得特别重要，因为前n名可以获得星星（含并列）。今天，J老师公布了上一次周测中班级同学的成绩，希望你能对他们进行排名，以此确定获得星星的人选。

Format

Input

第1行为两个整数，表示学生人数m和可以获得星星的排名n（n≤m）

第2至m+1行，每行为一个学生的姓名缩写和对应的成绩。

Output

第1至m行每行为该同学的排名和姓名，按排名从小到大输出结果；若排名相同，则按姓名缩写的字典序升序排列（为了避免内卷，就不用输出成绩了）。

第m+1行为一个整数，表示可以获得星星的人数s

Samples

6 3
jcw 42
sxz 48
mjx 46
cjw 46
tpx 46
tyy 45

1:sxz
2:cjw
2:mjx
2:tpx
5:tyy
6:jcw
4

Limitation

1s, 1024KiB for each test case.