Сортування злиттям

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

1. Якщо один робот у новому списку знаходиться раніше іншого, то основний номер першого менше або дорівнює основному номеру другого.

2. Якщо основні номери роботів рівні, то вони розміщені у такому ж порядку, як і у заданому списку.

Тау Китяни звернулись до Вас з проханням переписати список. Допоможіть модернізації організацій!

Вхідні дані

У першому рядку вхідного файлу знаходиться число N (1 ≤ N ≤ 100000) - кількість роботів на заводі. У кожному наступному рядку знаходяться 2 числа - основний та допоміжний номери чергового робота. Обидва номери невід'ємні і не перевищують 10^9.

Вихідні дані

Виведіть N рядків, i-ий містить 2 числа - основний та допоміжний номер i-го робота у новому списку.

Приклади