eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

  2. Если основные номера роботов равны, то они расположены в таком же порядке, как и в исходном списке.

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

Input data

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

Output data

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

Examples

Input example #1
10
1 8
8 9
2 10
1 11
4 2
7 2
3 11
2 23
3 3
6 7
Output example #1
1 8
1 11
2 10
2 23
3 11
3 3
4 2
6 7
7 2
8 9