Trước khi làm bài này hãy đọc kiểu dữ liệu Struct trong tài liệu

Sơn Tùng M-TP có rất nhiều người hâm mộ, không chỉ yêu thích ca sĩ này mà người hâm mộ còn thực hiện nhiều hoạt động nhằm thu hút thêm sự cổ vũ ca sĩ này từ những người khác. Trong một chuyến biểu diễn, Sơn Tùng gặp \(N\) người hâm mộ và anh phải dành một khoảng thời gian để ký tặng người hâm mộ của mình. Giả sử khoảng thời gian của Sơn Tùng chỉ đủ để ký cho \(T\) người hâm mộ và tất nhiên anh ấy muốn ưu tiên ký cho những ai có nhiều công lao với mình. Mỗi người hâm mộ được biết đến qua 2 thông tin \(< name, points >\), với ý nghĩa là tên và điểm cống hiến.

Bạn hãy chọn giúp Sơn Tùng danh sách \(T\) người hâm mộ để anh ta ký tặng với tiêu chí: ưu tiên người có điểm cống hiến cao, nếu có nhiều người có cùng điểm cống hiến thì ưu tiên người có tên nhỏ hơn theo trật tự từ điển.

Đầu vào
● Dòng đầu chứa hai số nguyên \(N\) và \(T\).
● Dòng thứ \(i\) trong \(N\) dòng sau chứa thông tin về người hâm mộ thứ \(i\), gồm \(name_i\) và \(points_j\)

Ràng buộc
● \(1≤T≤N≤10^5\);
● \(1 ≤ |name| ≤20\), \(1 ≤points ≤ 10^9\)

Đầu ra
In ra \(T\) dòng, mỗi dòng chứa tên một người hâm mộ theo trật tự ưu tiên như đã yêu cầu trong đề bài.

input

3  2
Hai  3
Hang  3
Nam  5

output

Nam
Hai