Petya recieved a gift of a string *s* with length up to 10<sup class="upper-index">5</sup> characters for his birthday. He took two more empty strings *t* and *u* and decided to play a game. This game has two possible moves:
 -  Extract the first character of *s* and append *t* with this character. -  Extract the last character of *t* and append *u* with this character. 
Petya wants to get strings *s* and *t* empty and string *u* lexicographically minimal.

You should write a program that will help Petya win the game.
First line contains non-empty string *s* (1 ≤ |*s*| ≤ 10<sup class="upper-index">5</sup>), consisting of lowercase English letters.
none
cab
abc
acdb
abdc
a
a
ab
ab
ba
ab
dijee
deeji
bhrmc
bcmrh
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bababaaababaabbbbbabbbbbbaaabbabaaaaabbbbbaaaabbbbabaabaabababbbabbabbabaaababbabbababaaaaabaaaabbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bccbbcccbccbacacbaccaababcbaababaaaaabcaaabcaacbabcaababaabaccacacccbacbcacbbbaacaaccccabbbbacbcbbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbcbcbbbbcccccbbbccbcbccccccbbbcbbccbcbbbbcbbccbccbccbcccbbccb
eejahjfbbcdhbieiigaihidhageiechaadieecaaehcehjbddgcjgagdfgffdaaihbecebdjhjagghecdhbhdfbedhfhfafbjajg
aaaaaaaaaaaaagjjbffhfhdebfdhbhdcehggjhjdbecebhidffgfdggjcgddbjhecheceeidhceieghdihigiieibhdcbbfjhjee
bnrdfnybkzepmluyrhofwnwvfmkdwolvyzrqhuhztvlwjldqmoyxzytpfmrgouymeupxrvpbesyxixnrfbxnqcwgmgjstknqtwrr
bbbbcggjknqrrwttsmwqnxfrnxixysepvrxpuemyuogrmfptyzxyomqdljwlvtzhuhqrzyvlowdkmfvwnwfohryulmpezkynfdrn
bcaeaae
aaaecbe
edcadcbcdd
abccdcddde
a
a
a
a
a
a
b
b
b
b
a
a
c
c
a
a
b
b
c
c
b
b
a
a
e
e
b
b
b
b
aa
aa
aa
aa
aa
aa
aa
aa
bb
bb
bb
bb
ba
ab
ca
ac
ab
ab
cb
bc
bb
bb
aa
aa
da
ad
ab
ab
cd
cd
aaa
aaa
aaa
aaa
aaa
aaa
aab
aab
aaa
aaa
baa
aab
bab
abb
baa
aab
ccc
ccc
ddd
ddd
ccd
ccd
bca
acb
cde
cde
ece
cee
bdd
bdd
aaaa
aaaa
aaaa
aaaa
aaaa
aaaa
abaa
aaab
abab
aabb
bbbb
bbbb
bbba
abbb
caba
aabc
ccbb
bbcc
abac
aabc
daba
aabd
cdbb
bbdc
bddd
bddd
dacb
abcd
abcc
abcc
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
baaab
aaabb
aabbb
aabbb
aabaa
aaaab
abcba
aabcb
bacbc
abbcc
bacba
aabcb
bdbda
adbdb
accbb
abbcc
dbccc
bcccd
decca
acced
dbbdd
bbddd
accec
accce
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaaaa
aaaaaa
bbbbab
abbbbb
bbbbab
abbbbb
aaaaba
aaaaab
cbbbcc
bbbccc
aaacac
aaaacc
bacbbc
abbbcc
cacacc
aacccc
badbdc
abbcdd
ddadad
aadddd
ccdece
cccede
eecade
acdeee
eabdcb
abbcde
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaabbaa
aaaaabb
baaabab
aaaabbb
bbababa
aaabbbb
bcccacc
acccbcc
cbbcccc
bbccccc
abacaaa
aaaaacb
ccdbdac
acdbdcc
bbacaba
aaabcbb
abbaccc
aabbccc
bdcbcab
abcbcdb
dabcbce
abbccde
abaaabe
aaaabbe
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
ababbbba
aaabbbbb
aaaaaaba
aaaaaaab
babbbaab
aaabbbbb
bcaccaab
aaabcccb
bbccaabc
aabccbbc
cacaaaac
aaaaaccc
daacbddc
aabccddd
cdbdcdaa
aadcdbdc
bccbdacd
acdbccbd
abbeaade
aaadebbe
ccabecba
aabcebcc
ececaead
aadecece
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aabaaabbb
aaaaabbbb
abbbbbaab
aaabbbbbb
bbbaababb
aaabbbbbb
babcaaccb
aaabcccbb
ccbcabaac
aaabcbccc
caaaccccb
aaabccccc
abbcdbddb
abbbbdddc
dbcaacbbb
aabbbccbd
cadcbddac
aacddbcdc
ecebadadb
aabddbece
bdbeeccdd
bbccddeed
daaedecda
aaadceded
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
abaaaaabbb
aaaaaabbbb
bbaaaabaaa
aaaaaaabbb
bbabbaaaaa
aaaaaabbbb
cbaabcaacc
aaaacbbccc
aaaaccccab
aaaaabcccc
bccaccaacc
aaaccccbcc
dbdccdcacd
accdccdbdd
caaddaaccb
aaaabccddc
adbbabcbdc
aabbbbccdd
cdeabdbbad
aabbdbdedc
eeddcbeeec
bcceeeddee
bbcebddeba
abeddbecbb
import sys
from types import GeneratorType

inf = float("inf")


class FastIO:
    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(" ".join(str(w) for w in x) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, stack=[]):
        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to

        return wrappedfunc


class SuffixArray:
    def __init__(self, ind):
        self.ind = ind
        return

    def doubling(self, s):
        # sa[i]:排名为i的后缀的起始位置
        # rk[i]:起始位置为i的后缀的排名
        # height[i]: 第i名的后缀与它前一名的后缀的最长公共前缀
        n = len(s)
        sa = []
        rk = []
        for i in range(n):
            rk.append(self.ind[s[i]])  # 刚开始时，每个后缀的排名按照它们首字母的排序
            sa.append(i)  # 而排名第i的后缀就是从i开始的后缀

        l = 0  # l是已经排好序的长度，现在要按2l长度排序
        sig = len(self.ind)  # sig是unique的排名的个数，初始是字符集的大小
        while True:
            p = []
            # 对于长度小于l的后缀来说，它们的第二关键字排名肯定是最小的，因为都是空的
            for i in range(n - l, n):
                p.append(i)
            # 对于其它长度的后缀来说，起始位置在`sa[i]`的后缀排名第i，而它的前l个字符恰好是起始位置为`sa[i]-l`的后缀的第二关键字
            for i in range(n):
                if sa[i] >= l:
                    p.append(sa[i] - l)
            # 然后开始基数排序，先对第一关键字进行统计
            # 先统计每个值都有多少
            cnt = [0] * sig
            for i in range(n):
                cnt[rk[i]] += 1
            # 做个前缀和，方便基数排序
            for i in range(1, sig):
                cnt[i] += cnt[i - 1]
            # 然后利用基数排序计算新sa
            for i in range(n - 1, -1, -1):
                cnt[rk[p[i]]] -= 1
                sa[cnt[rk[p[i]]]] = p[i]

            # 然后利用新sa计算新rk
            def equal(i, j, l):
                if rk[i] != rk[j]:
                    return False
                if i + l >= n and j + l >= n:
                    return True
                if i + l < n and j + l < n:
                    return rk[i + l] == rk[j + l]
                return False

            sig = -1
            tmp = [None] * n
            for i in range(n):
                # 直接通过判断第一关键字的排名和第二关键字的排名来确定它们的前2l个字符是否相同
                if i == 0 or not equal(sa[i], sa[i - 1], l):
                    sig += 1
                tmp[sa[i]] = sig
            rk = tmp
            sig += 1
            if sig == n:
                break
            # 更新有效长度
            l = l << 1 if l > 0 else 1
        # 计算height数组
        k = 0
        height = [0] * n
        for i in range(n):
            if rk[i] > 0:
                j = sa[rk[i] - 1]
                while i + k < n and j + k < n and s[i + k] == s[j + k]:
                    k += 1
                height[rk[i]] = k
                k = max(0, k - 1)  # 下一个height的值至少从max(0,k-1)开始
        return sa, rk, height


def main(ac=FastIO()):
    words = [chr(i + ord("a")) for i in range(26)]
    ind = {st: i for i, st in enumerate(words)}
    nt = SuffixArray(ind)

    s = ac.read_str()
    n = len(s)
    sa, rk, height = nt.doubling(s)
    post = [inf]*(n+1)
    for i in range(n-1, -1, -1):
        post[i] = ac.min(post[i+1], rk[i])
    ans = []
    stack = []
    for i in range(n):
        stack.append(i)
        while stack and rk[stack[-1]] < post[i+1]:
            ans.append(s[stack.pop()])

    ans.extend(stack[::-1])
    ac.st("".join(ans))
    return


main()
