Знайдіть \(K\)-ий лексикографічно найменший рядок серед рядків, які є перестановками рядка \(S\).

Формат вхідних даних

Вхідний потік містить рядок \(S\) (\(1 \le |S| \le 8\)), який складається з малих англяйський літер.

Є принаймні \(K\) окремі рядки, які є перестановками \(S\).

Формат вихідних даних

У вихідний потік виведіть шуканий рядок.

Примітка

До прикладу 1:

Існує три перестановки рядка aab: {{ aab, aba, baa }}. 2-й лексикографічно найменший з них — aba.

Приклад вхідних даних

aab 2

Приклад вихідних даних

aba

Приклад вхідних даних

baba 4

Приклад вихідних даних

baab

Приклад вхідних даних

ydxwacbz 40320

Приклад вихідних даних

zyxwdcba