eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сортировка слиянием

Сортировка слиянием

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В связи с модернизацией производства на заводе зубных щёток в Тау Кита было решено переписать список роботов, обслуживающих завод. Каждый робот имеет два номера: основной и вспомогательный. Новый список должен удовлетворять следующим правилам:

  1. Если один робот в новом списке находится раньше другого, то основной номер первого меньше или равен основному номеру второго.

  2. Если основные номера роботов равны, то они расположены в таком же порядке, как и в исходном списке.

Тау Китяне обратились к Вам с просьбой переписать список. Помогите модернизации организаций!

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

В первой строке находится количество n (1 n 100000) роботов на заводе. В каждой следующей строке находятся два числа - основной и вспомогательный номера очередного робота. Оба номера неотрицательны и не превосходят 10^9.

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

Выведите n строк, i-я из которых содержит два числа - основной и вспомогательный номер i-го робота в новом списке.

Пример

Входные данные #1
10
1 8
8 9
2 10
1 11
4 2
7 2
3 11
2 23
3 3
6 7
Выходные данные #1
1 8
1 11
2 10
2 23
3 11
3 3
4 2
6 7
7 2
8 9