Сапожнику необходимо выполнить n работ. Каждый день сапожник может выполнять только одну работу. Для каждой i - ой работы известно время ее выполнения в днях Ti и штраф Si, который каждый день должен платить сапожник до тех пор, пока он не отдаст i - ую работу заказчику. Найти последовательность выполнения работ, при которой сумма штрафа будет минимальной.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит количество работ n (1 ≤ n ≤ 1000), за которой следуют n строк, содержащие характеристики работ Ti (1 ≤ Ti ≤ 1000) и Si (1 ≤ Si ≤ 10000).

Выходные данные

Для каждого теста в отдельной строке вывести порядок работ, при котором сумма штрафа минимальна. При существовании нескольких оптимальных порядков работ выводить лексикографически наименьший.