Задача G. Сортировка подсчетом

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб
Максимальный балл:10  

Условие

Набором данных называется пара чисел первое из которых называется ключом, второе — данными. Ваша задача состоит в том, чтобы упорядочить данные в порядке возрастания ключей. При совпадении ключей первым в отсортированном массиве должен идти тот же элемент что и в не сортированном.

Формат входного файла

Во входном файле содержится число N, за которым следуют N пар чисел — наборы данных.

Формат выходного файла

В выходном файле должно содержаться ровно N чисел — данные, упорядоченные в порядке возрастания ключей.

Ограничения

0 ≤ N ≤ 100000, все числа находятся в диапазоне от 1 до 100000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 1
3 2 
2 3
3 4
1 3 2 4

0.032s 0.007s 15