Сортировка слиянием
В связи с модернизацией производства на заводе зубных щёток в Тау Кита было решено переписать список роботов, обслуживающих завод. Каждый робот имеет два номера: основной и вспомогательный. Новый список должен удовлетворять следующим правилам:
Если один робот в новом списке находится раньше другого, то основной номер первого меньше или равен основному номеру второго.
Если основные номера роботов равны, то они расположены в таком же порядке, как и в исходном списке.
Тау Китяне обратились к Вам с просьбой переписать список. Помогите модернизации организаций!
Входные данные
В первой строке находится количество n (1 ≤ n ≤ 100000) роботов на заводе. В каждой следующей строке находятся два числа - основной и вспомогательный номера очередного робота. Оба номера неотрицательны и не превосходят 10^9.
Выходные данные
Выведите n строк, i-я из которых содержит два числа - основной и вспомогательный номер i-го робота в новом списке.