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