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

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

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

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