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

Вхідні дані

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

Вихідні дані

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