Устойчивая сортировка

Каждая запись — это ключ и значение. Отсортируйте записи по неубыванию ключа.

Записи с одинаковым ключом обязаны сохранить исходный порядок.

В первой строке $n$ от $1$ до $10^5$. Далее $n$ строк, в каждой ключ и значение, оба по модулю не больше $10^9$.

Одна строка: значения записей в нужном порядке.

Обычный std::sort порядок равных не сохраняет — замер показал, что он ломается уже на сотне элементов. Нужен std::stable_sort. Другой путь — добавить в ключ исходный номер и сортировать пару обычным sort; так делают, когда важна скорость.