В армии некоторого государства построение солдат по росту производится следующим образом:
сначала выбирается самый высокий солдат, после чего он несколькими последовательными переменами
местами с непосредственными соседями передвигается в начало строя. Далее выбирается самый
высокий из оставшихся и ставится на второе место и т. д. Если в строю несколько солдат имеют наибольший
рост, то из них выбирается тот, который стоит ближе к началу строя.
Один талантливый полководец заметил, что построение таким образом занимает слишком много времени,
и предложил своему начальнику новый способ решения этой задачи. Начальник, будучи человеком
консервативным, усомнился в способе, предложенным своим подчиненным, и предложил простой
способ проверки: построить солдат старым образом, переписать имена солдат в порядке обхода
строя от самого высокого к самому низкому, после чего повторить эту процедуру для нового способа
и сравнить результаты.
В результате выполнения многократных проверок начальник убедился в правоте своего подчиненного.
Реализуйте один из способов, которым мог решить задачу талантливый полководец.
Формат входного файла
Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата:
рост Ri и имя Si.
Формат выходного файла
Выходной файл должен содержать N строк, в каждой из которых содержится имя очередного солдата из
строя, упорядоченного по росту от большего к меньшему.
Ограничения
1≤N≤1000000≤Ri≤1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.