Игра «Что? Где? Когда?»

Несколько команд участвуют в турнире по игре «Что? Где? Когда?». Согласно регламенту турнира, в финал проходит половина команд (с округлением вверх), набравшие больше правильных ответов, чем остальные. Помогите жюри сформировать итоговый протокол.

Формат ввода

На первой строке указано натуральное число N — количество команд.

Далее следует описание результатов N команд в произвольном порядке. Данные о каждой команде записываются на двух строках: на первой — название команды, на второй — количество правильных ответов. Гарантируется, что количество правильных ответов у всех команд разное.

Формат вывода

Нужно вывести на отдельных строках сначала в алфавитном порядке названия всех команд, вышедших в финал (т. е. команд из лучшей по количеству ответов половины), а затем названия всех остальных команд (также на отдельных строках в алфавитном порядке).

Пример

Ввод

4

Уважаемые знатоки

22

Обожаемые знатоки

20

Магистры

24

Яндекс.Лицеисты

23

Вывод

Магистры

Яндекс.Лицеисты

Обожаемые знатоки

Уважаемые знатоки