Problem description

Jasio postanowił być interesujący i podrywać dziewczyny na następujący patent: Patrz maleńka, pokażę Ci K-tą liczbę w dziwnej kolejności.

“Maleńka” postanowiła pociągnąć temat i pogrążyć Jasia jeszcze bardziej niż sam się pogrążył głupimi tekstami. Zapytała więc Jasia: A co to jest dziwna kolejność? Jasio wyjaśnił więc, że ułoży wszystkie liczby naturalne od 1 do 10¹⁸ − 1 włącznie (wszystkie liczby co najwyżej 18-cyfrowe) według największej cyfry (ta liczba, która ma mniejszą największą cyfrę jest wcześniej w kolejności). Przykładowo: liczba 25 będzie w kolejności Jasia wcześniej niż liczba 16. I z tak uporządkowanego ciągu liczb, Jasio rzekomo szybko wybierze K-tą liczbę.

Maleńka nie jest jednak w ciemię bita i szybko skontrowała: A co jak dwie liczby mają tę samą największą cyfrę? Ot choćby 159 i 942? Jasio musiał się chwilę namyślić, bo nie przewidział tak skomplikowanego pytania. Odpowiedział: Wtedy porównujemy według drugiej największej cyfry. A jak to nie przynosi rozwiązania to według trzeciej największej. I tak dalej, maleńka. Łapiesz? Przykładowo, oznaczałoby to, że 942 jest wcześniej w kolejności niż 159.

Maleńka oczywiście szybko złapała, ale że przewyższa Jasia intelektem zapytała ponownie: A co jak liczby są różnej długości i porównując dwie liczby w jednej z nich skończyły się już cyfry do porównania, a w drugiej nie? Ot choćby 253 i 5 321? Ponownie trudne pytanie, Jasio znowu musiał pomyśleć. Wymyślił coś takiego: Wtedy ta liczba, której cyfr zabrakło jest mniejsza. Czyli w tym przykładzie wychodziłoby na to, że 253 jest wcześniej w kolejności niż 5 321.

Jasio już tryumfował, gdy Maleńka postanowiła znowu zadać cios: A co jeśli liczby mają taki sam (multi)zbiór cyfr ale w innej kolejności? Wtedy według Twoich zasad są nieporównywalne! Ha! I co wtedy? Weź na przykład 502 i 250. Jasio czuje, że rzeczywiście się skompromitował, ale musi ciągnąć dyskusję dalej. Takie są zasady udanego podrywu. Odparł więc: To niech wtedy działa normalne porównanie liczb. Wcześniej jest po prostu ta mniejsza liczba. Oznacza to, że 250 jest wcześniej w kolejności niż 502.

No świetnie. Maleńka poczuła się umiarkowanie usatysfakcjonowana, bo chociaż teraz da się jakoś sprawdzić czy Jasio nie kantuje, że rzekomo potrafi szybko liczyć takie trudne rzeczy nie umiejąc ich precyzyjnie zdefiniować. Dobrze Jasio. To jaka jest K-ta liczba w tym Twoim dziwnym sortowaniu? Jasio ma tylko “dobrą” bajerę, ale rzeczywiście nie umie takich trudnych rzeczy. Naiwnie wierzy, że od sukcesu w tym podrywie dzieli go tylko prawidłowa odpowiedź na to pytanie. Pomożesz mu zanim Maleńka sobie pójdzie do innego?

Napisz program, który wczyta liczbę K, wyznaczy K-tą liczbę w dziwnym sortowaniu Jasia i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna K.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – K-ta liczba w posortowaniu liczb {1, 2, …, 10¹⁸ − 1} według metody Jasia.

Ograniczenia

1 ≤ K ≤ 10¹⁸ − 1.

Przykład

23

1010