A-C transfer

from bisect import bisect_left, bisect_right
from sys import stdin, stdout, maxsize


R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))

output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))

# solution starts from here

a = list(R())

stack = []
next_smallest = len(a)*[-1]

for i in range(len(a)):
    while len(stack) and a[stack[-1]] > a[i]:
        stack.pop(-1)
    if len(stack):
        next_smallest[stack[-1]] = i
    stack.append(i)

i =  a.index(min(a))
ans = [a[i]]
stack = a[:i]

while i < len(a) and i > -1:
    while len(stack) and next_smallest[i]>-1 and stack[-1] < a[next_smallest[i]]:
        ans.append(stack[-1])
        stack.pop()
    if next_smallest[i] > -1:
        stack += a[i+1:next_smallest[i]]
        ans.append(a[next_smallest[i]])
    i = next_smallest[i]

stack.reverse()
ans += stack

output(''.join(ans))