菠萝的成绩单

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

考完试以后,菠萝获得了一个含有 n 个成绩的成绩单,他要把成绩按照从高到低排序,如果成绩相同则按照学生编号从小到大排序。

老师为了检验菠萝是否把成绩排序对了,会询问前 m 高的成绩及该学生的编号,你能帮菠萝回答老师的询问吗?

Input

输入数据有多组(数据组数不超过 10),到 EOF 结束。

对于每组数据:

  • 第一行输入成绩的个数 n 以及 m (1 <= n <= 100000, 1 <= m <= n)
  • 接下来的 n 行,每行输入 2 个正整数,分别为学生编号 id (1 <= id <= n),成绩 ai (1 <= ai <= 10000)

当 n 和 m 同时为 0 时结束程序。

Output

对于每组数据:

  • 第一行输出 "Case #x:" (输出不包括引号,且冒号后无空格),x 表示当前为第几组数据
  • 之后输出 m 行。每行格式按照 "编号 成绩" 的格式输出

Sample Input

3 1
1 1
2 2
3 3
5 3
4 2
2 2
1 1
3 3
5 2
0 0

Sample Output

Case #1:
3 3
Case #2:
3 3
2 2
4 2

Hint

请大家仔细核对 "Case #x:",建议复制样例输出的模式以防输出时不符合题目要求而导致的 Wrong Answer。

数据量较大,请使用高效排序算法。

Source

【2016级《程序设计基础(B)II》期末上机考试-第一场】MLE_kenan