Ускорение алгоритма ранжирования

На ранних этапах турнира инженеры-программисты использовали алгоритм ранжирования, основанный на пузырьковой сортировке. Когда участников было мало, это работало нормально. Но теперь команд стало слишком много, и вас просят ускорить алгоритм.

У каждой команды есть уникальный номер (идентификатор) и набранный ею результат (счёт). Необходимо упорядочить команды по убыванию результатов (сначала команды с наибольшими очками, в конце — с наименьшими). При этом команды, набравшие одинаковое количество очков, должны следовать в том же порядке, в каком они шли во входных данных. Значит, требуется стабильная сортировка.

Входные данные

Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ ).

Следующие n строк содержат разделённые пробелом пары (), описывающие уникальный идентификатор команды и её результат.

Выходные данные

Программа должна вывести n строк. В каждой строке нужно указать два целых числа: id команды и её результат.

Примеры