Người hâm mộ nhiệt thành nhất

Trong một buổi tuyển chọn cầu thủ, FullHouse Dev được giao nhiệm vụ phân tích dữ liệu của các fan hâm mộ để chọn ra những người may mắn được gặp gỡ cầu thủ ngôi sao. Với sự nhiệt huyết và kỹ năng phân tích dữ liệu, FullHouse Dev bắt đầu giải quyết bài toán này.

Bài toán

FullHouse Dev nhận được danh sách \(N\) fan hâm mộ và thông tin rằng cầu thủ ngôi sao chỉ có thể gặp gỡ tối đa \(T\) người. Mỗi fan được định nghĩa bởi hai thông số: Tên và Chỉ số Fan. Chỉ số Fan càng cao thể hiện sự cuồng nhiệt càng lớn. Nhiệm vụ của FullHouse Dev là chọn ra \(T\) fan để cầu thủ gặp gỡ, ưu tiên những người có Chỉ số Fan cao hơn. Trong trường hợp có Chỉ số Fan bằng nhau, họ sẽ chọn người có tên đứng trước theo thứ tự từ điển.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(T\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi và một số nguyên cách nhau bởi khoảng trắng. Chuỗi là tên của fan, số nguyên là Chỉ số Fan.

OUTPUT FORMAT:

• In ra \(T\) dòng, mỗi dòng chứa tên của một fan được chọn. Fan có Chỉ số Fan cao hơn được in trước, nếu bằng nhau thì in tên đứng trước theo thứ tự từ điển.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq T \leq N\)
• \(1 \leq \text{Chỉ số Fan} \leq 10^9\)
• Tên chỉ bao gồm các ký tự trong tập [a-z].
• Không đảm bảo các tên là duy nhất.

Ví dụ

INPUT

3 2
surbhi 3
surpanakha 3
shreya 5

OUTPUT

shreya
surbhi

Giải thích

Thứ tự sắp xếp của các fan sẽ là {"shreya", "surbhi", "surpanakha"}. Do đó, hai fan được chọn là shreya và surbhi.