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

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

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

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

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

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

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

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