ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1100. Таблица результатов

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Старое программное обеспечение для проведения соревнований использует пузырьковую сортировку для создания таблицы результатов. Однако сейчас команд слишком много, и программное обеспечение работает слишком медленно. Вас попросили написать программу, которая создаёт такую же таблицу результатов, как и старое программное обеспечение, но быстро.

Исходные данные

Первая строка входных данных содержит только целое число 1 < N ≤ 150 000 — количество команд. Каждая из следующих N строк содержит два целых числа: 1 ≤ ID ≤ 107 и 0 ≤ M ≤ 100. ID — уникальный номер команды, а M — количество решённых этой командой задач.

Результат

Вывод должен содержать N строк с двумя целыми числами ID и M в каждой. Строки должны идти по убыванию M в порядке, полученном с помощью пузырьковой сортировки (см. ниже).

Пример

исходные данныерезультат
8
1 2
16 3
11 2
20 3
3 5
26 4
7 1
22 4
3 5
26 4
22 4
16 3
20 3
1 2
11 2
7 1

Замечания

Пузырьковая сортировка работает следующим образом:
пока существуют A[i] и A[i+1], такие что A[i] < A[i+1],
   обменять(A[i], A[i+1]);
Автор задачи: Павел Атнашев
Источник задачи: Tetrahedron Team Contest May 2001