Сортування злиттям#4037
У зв'язку з модернізацією виробництва на заводі зубних щіток у Тау Кита було вирішено переписати список роботів, які обслуговують завод. Кожен робот має два номери: основний та допоміжний. Новий список повинен задовольняти наступним правилам:
Якщо один робот у новому списку знаходиться раніше іншого, то основний номер першого менше або дорівнює основному номеру другого.
Якщо основні номери роботів рівні, то вони розміщені у такому ж порядку, як і у заданому списку.
Тау Китяни звернулись до Вас з проханням переписати список. Допоможіть модернізації організацій!
У першому рядку вхідного файлу знаходиться число (1 \le N \le 100000) - кількість роботів на заводі. У кожному наступному рядку знаходяться числа - основний та допоміжний номери чергового робота. Обидва номери невід'ємні і не перевищують 10^9.
Виведіть рядків, -ий містить числа - основний та допоміжний номер -го робота у новому списку.
Приклад 1