Petya recieved a gift of a string s with length up to 10^5 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.


-----Input-----

First line contains non-empty string s (1 ≤ |s| ≤ 10^5), consisting of lowercase English letters.


-----Output-----

Print resulting string u.


-----Examples-----
Input
cab

Output
abc

Input
acdb

Output
abdc

Difficulty: interview

Starter code:

Solutions:
from collections import deque
S = input()
mn = [ 300 for i in range( len( S ) ) ]
for i in range( len( S ) - 1, -1, -1 ):
  if i == len( S ) - 1:
    mn[ i ] = ord( S[ i ] )
  else:
    mn[ i ] = min( mn[ i + 1 ], ord( S[ i ] ) )
ans = ""
dq = deque()
for i in range( len( S ) ):
  dq.append( ord( S[ i ] ) )
  while len( dq ) and ( i + 1 == len( S ) or dq[ len( dq ) - 1 ] <= mn[ i + 1 ] ):
    ans += chr( dq[ len( dq ) - 1 ] )
    dq.pop()
print( ans )


from collections import defaultdict

s = input()
s = [x for x in s]

t, u = [], []

ds = defaultdict(int)

for c in s:
    ds[c] += 1

curr_letter_index = ord('a')
curr_poz_in_s = 0

while curr_letter_index <= ord('z'):
    curr_letter = chr(curr_letter_index)

    if len(t) > 0 and ord(t[-1]) <= ord(curr_letter):
        letter = t.pop()
        u.append(letter)
    else:
        if ds[curr_letter] > 0:
            letter = s[curr_poz_in_s]
            curr_poz_in_s += 1
            t.append(letter)
            ds[letter] -= 1
        else:
            curr_letter_index += 1

t.reverse()
print("".join(u + t))


s = input()
m = ['z' for i in range(len(s))]
m[-1] = s[-1]
c = s[-1]
for i in range(len(s) - 2, -1, -1):
    if s[i] < c:
        c = s[i]
    m[i] = c
ind = m.index(min(m))
l = []
res = ''
for i in range(len(s)):
    while l and l[-1] <= m[i]:
        res += l.pop()
    l.append(s[i])
print(res + ''.join(map(str, (l[::-1]))))


from queue import deque

dp = {}

def sol_1():
    idx = 0
    while True:
        min_idx = get_min_char_idx(s, idx)
        if min_idx == -1:
            break
        if len(t) > 0 and ord(t[-1]) <= ord(s[min_idx]):
            # we need to take t
            u.append(t.pop())
        else:
            # take up to min_idx
            t.extend(s[idx:min_idx+1])
            idx = min_idx+1

def efficient_sol():
    nonlocal u, t, s
    import string
    indices = {char: [] for char in string.ascii_lowercase}  # will hold indices for each char

    # fill indices
    for idx, char in enumerate(s):
        indices[char].append(idx)

    curr_idx = 0
    for char in string.ascii_lowercase:
        if curr_idx == len(s):
            break
        if len(t) > 0 and ord(char) >= ord(t[-1]):
            # We've started searching for bigger characters, so we need to empty the smaller ones first
            while len(t) > 0 and ord(char) >= ord(t[-1]):
                u.append(t.pop())

        for idx in sorted(indices[char]):
            if curr_idx == len(s):
                return
            min_idx = idx
            if min_idx < curr_idx:
                # we've passed this character
                continue
            elif min_idx == curr_idx:
                if len(t) > 0 and ord(char) > ord(t[-1]):
                    raise Exception()
                # we are at that character, so just add it
                u.append(char)
                curr_idx += 1
                continue
            # mid_idx is bigger, so we put everything up until this character in T
            # then, add the character himself
            t.extend(s[curr_idx:min_idx])
            u.append(char)
            curr_idx = min_idx + 1
    while curr_idx < len(s):
        pass

def get_min_char_idx(s: str, start_idx: int):
    nonlocal dp
    if start_idx >= len(s):
        return -1
    if start_idx in dp:
        return dp[start_idx]
    min_char = s[start_idx]
    min_idx = start_idx
    while start_idx < len(s):
        if ord(s[start_idx]) < ord(min_char):
            min_char = s[start_idx]
            min_idx = start_idx
        start_idx += 1
    dp[start_idx] = min_idx
    return min_idx

# aaaczbgjs
import string
s = input()
# s = 'abcadc'
# s = string.ascii_lowercase + string.ascii_lowercase

u = []
t = []

# if len(s) >= 10**3:
efficient_sol()
# else:
#     sol_1()

# abaaabababacba
# print(t)
print(''.join(u + list(reversed(t))))


s = input()
m = ['z' for i in range(len(s))]
m[-1] = s[-1]
c = s[-1]
for i in range(len(s) - 2, -1, -1):
    if s[i] < c:
        c = s[i]
    m[i] = c
ind = m.index(min(m))
l = []
res = ''
for i in range(len(s)):
    while l and l[-1] <= m[i]:
        res += l.pop()
    l.append(s[i])
print(res + ''.join(map(str, (l[::-1]))))


#! /bin/python

s = input()
resultBase = ""
resultRest = ""
best = len(s) - 1
mini = [0] * len(s)

for i in range(len(s) - 1, -1, -1):
    mini[i] = best
    if s[best] >= s[i]:
        best = i

for i in range(len(s)):
    resultRest += s[i]
    while len(resultRest) > 0 and resultRest[-1] <= s[mini[i]]:
        resultBase += resultRest[-1]
        resultRest = resultRest[:-1]
    
    #  print(resultRest[-1] if len(resultRest) > 0 else '-', s[mini[i]])
    #  print(resultRest)
    #  print(resultBase)
    #  print()
    

print(resultBase + resultRest[::-1])


'''input
cab
'''
s = input()
m = ["z"] * len(s)
m[-1] = s[-1]
c = s[-1]
for x in range(len(s) - 2, -1, -1):
	c = min(c, s[x])
	m[x] = c
i = m.index(min(m))
t = []
y = ""
for x in range(len(s)):
	while t and t[-1] <= m[x]:
		y += t.pop()
	t.append(s[x])
print(y, end="")
for x in t[::-1]:
	print(x, end="")
# s1 = sorted(s)
# t, u = [], []
# for l in s1:
# 	if l in s:
# 		i = s.index(l)
# 		t += s[:i]
# 		del s[:i+1]
# 		u.append(l)
# print("".join(u + t[::-1]))


import sys
import collections

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        del self.stack[len(self.stack)-1]

    def top(self):
        return self.stack[len(self.stack)-1]

    def empty(self):
        return len(self.stack) == 0

def main():
    s = list(sys.stdin.readline().split()[0])

    hist = [0 for i in range(256)]

    for c in s:
        hist[ord(c)]+=1

    cur = 0
    u = []
    t = []

    minn = ord('a')
    for i in range(minn, ord('z')+1):
        if(hist[i]):
            minn = i
            break
    aux = []
    while cur < len(s):
        aux.append(s[cur])
        hist[ord(s[cur])] -= 1

        if(s[cur] == chr(minn)):
            u += aux
            aux = []
            minn = ord('z')
            for i in range(ord('a'), ord('z')+1):
                if(hist[i]):
                    minn = i
                    break

            while(len(u) and ord(u[-1]) <= minn):
                t.append(u[-1])
                del u[-1]
        cur += 1


    print("".join(t))





main()

# argc, argv
# wait_pid
# sig_alarm


import sys
import collections

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        del self.stack[len(self.stack)-1]

    def top(self):
        return self.stack[len(self.stack)-1]

    def empty(self):
        return len(self.stack) == 0

def main():
    s = list(sys.stdin.readline().split()[0])

    hist = [0 for i in range(256)]

    for c in s:
        hist[ord(c)]+=1

    cur = 0
    u = []
    t = []

    minn = ord('a')
    for i in range(minn, ord('z')+1):
        if(hist[i]):
            minn = i
            break
    aux = []
    while cur < len(s):
        aux.append(s[cur])
        hist[ord(s[cur])] -= 1

        if(s[cur] == chr(minn)):
            u += aux
            aux = []
            minn = ord('z')
            for i in range(ord('a'), ord('z')+1):
                if(hist[i]):
                    minn = i
                    break

            while(len(u) and ord(u[-1]) <= minn):
                t.append(u[-1])
                del u[-1]
        cur += 1


    print("".join(t))

main()


import sys
import collections

def main():
    s = list(sys.stdin.readline().split()[0])

    hist = [0 for i in range(256)]

    for c in s:
        hist[ord(c)]+=1

    cur = 0
    u = []
    t = []

    minn = ord('a')
    for i in range(minn, ord('z')+1):
        if(hist[i]):
            minn = i
            break
    aux = []
    while cur < len(s):
        aux.append(s[cur])
        hist[ord(s[cur])] -= 1

        if(s[cur] == chr(minn)):
            u += aux
            aux = []
            minn = ord('z')
            for i in range(ord('a'), ord('z')+1):
                if(hist[i]):
                    minn = i
                    break

            while(len(u) and ord(u[-1]) <= minn):
                t.append(u[-1])
                del u[-1]
        cur += 1


    print("".join(t))

main()


from itertools import takewhile

def f(s):
    t = []
    u = []
    chars = 'abcdefghijklmnopqrstuvwxyz'

    for c in chars:
        stack = list(takewhile(lambda x: x <= c, reversed(t)))
        count = len(stack)
        if count > 0:
            u += stack
            t = t[:-count]

        count = s.count(c)
        if count > 0:
            rindex = s.rindex(c)
            u += c * count
            t += [x for x in s[:rindex] if x != c]
            s = s[rindex + 1:]

    u += reversed(t)
    return ''.join(u)

print(f(input()))


#! /bin/python

s = input()
resultBase = ""
resultRest = ""
best = len(s) - 1
mini = [0] * len(s)

for i in range(len(s) - 1, -1, -1):
    mini[i] = best
    if s[best] >= s[i]:
        best = i

for i in range(len(s)):
    resultRest += s[i]
    while len(resultRest) > 0 and resultRest[-1] <= s[mini[i]]:
        resultBase += resultRest[-1]
        resultRest = resultRest[:-1]
    
print(resultBase + resultRest[::-1])


s = input()
iterate = 0
e = [(True) for i in range(len(s))]
ans = ['' for i in range(len(s))]
idx = 0

lastOccur = [-1 for i in range(26)]

for i in range (len(s)):
	lastOccur[ord(s[i])-ord('a')] = i

i = 0
while(i < 26 and iterate < len(s)):
	j = iterate-1
	while(j >= 0 and ord(s[j]) - ord('a') <= i):
		if(e[j]):
			ans[idx] = s[j]
			e[j] = False
			idx += 1
		j -= 1

	j = iterate
	while(j < lastOccur[i]+1):
		if(e[j] and ord(s[j])-ord('a') == i):
			ans[idx] = s[j]
			e[j] = False
			idx += 1
		j += 1
	iterate = j
	i += 1

if(iterate >= len(s)):
	for j in range(len(s)-1, -1, -1):
		if(e[j]):
			ans[idx] = s[j]
			idx += 1


#print(ans)
str1 = ''.join(ans)
print(str1)

s=input()
s+=('{')
ans=""
tmp=[]
m = ['z' for i in range(len(s)+1)]
for i in range(len(s)-1,-1,-1):
    m[i]=min(m[i+1],s[i])
#print(m)
for i in range(len(s)-1):
    tmp.append(s[i])
    while len(tmp) and tmp[-1]<=m[i+1]:
            ans += tmp.pop()
print(ans)


def s_has_smaller(s_cnt_local, c):
    for i in range(ord('a'), ord(c)):
        if s_cnt_local[i] > 0:
            return True
    return False


s = list(input())
s.reverse()


t = []
u = []

s_cnt = [0] * (ord('z')+1)
for x in s:
    s_cnt[ord(x)] += 1


while s or t:
    # print('+'*10)
    # print(s)
    # print(t)
    # print(u)
    # print(s_cnt)
    # print(t_cnt)
    if not s:
        while t:
            u.append(t.pop())
    elif not t:
        x = s.pop()
        s_cnt[ord(x)] -= 1
        t.append(x)
    else:
        if s_has_smaller(s_cnt, t[-1]):
            x = s.pop()
            s_cnt[ord(x)] -= 1
            t.append(x)
        else:
            x = t.pop()
            u.append(x)

print("".join(u))



ptr = ord('a')


def s_has_smaller(s_cnt_local, c):
    nonlocal ptr
    for i in range(ptr, ord(c)):
        ptr = i
        if s_cnt_local[i] > 0:
            return True
    return False


s = list(input())
s.reverse()


t = []
u = []

s_cnt = [0] * (ord('z')+1)
for x in s:
    s_cnt[ord(x)] += 1


while s or t:
    # print('+'*10)
    # print(s)
    # print(t)
    # print(u)
    # print(s_cnt)
    # print(t_cnt)
    if not s:
        while t:
            u.append(t.pop())
    elif not t:
        x = s.pop()
        s_cnt[ord(x)] -= 1
        t.append(x)
    else:
        if s_has_smaller(s_cnt, t[-1]):
            x = s.pop()
            s_cnt[ord(x)] -= 1
            t.append(x)
        else:
            x = t.pop()
            u.append(x)

print("".join(u))


def letters():
    return (chr(i) for i in range(ord('a'), ord('z') + 1))


s = input()

ls = {lt: 0 for lt in letters()}

for lt in s:
    ls[lt] += 1

s = [ch for ch in reversed(s)]
stack = []
res = []

for curr in letters():
    while stack and stack[-1] <= curr:
        res.append(stack.pop(-1))
    while ls[curr] > 0:
        if s[-1] != curr:
            c = s.pop(-1)
            ls[c] -= 1
            stack.append(c)
        else:
            ls[curr] -= 1
            res.append(s.pop(-1))
res += reversed(stack)
print(''.join(res))


s=input()
n=len(s)
cur=('z',n)
mi=[cur for _ in range(n)]
ns=mi[:]
for i in range(n-1,-1,-1):
    if (s[i],i)<cur:
        cur=(s[i],i)
    mi[i]=cur
    ns[i]=(s[i],i)
pos=0
cache=list()
res=''

while len(res)<n:
    c,i=mi[pos]
    res+=c
    cache+=ns[pos:i]
    pos=i
    if  cache:
        val, _ =cache[-1]
        mi[pos]=(val,pos)
        ns[pos]=(val,pos)
        if pos<n-1:
            mi[pos]=min(mi[pos],mi[pos+1])
        cache.pop()
    else:
        pos+=1
        
        
print( res   ) 


s=input()
n=len(s)
cur=('z',n)
mi=[cur for _ in range(n)]
ns=['z']*n
for i in range(n-1,-1,-1):
    if (s[i],i)<cur:
        cur=(s[i],i)
    mi[i]=cur
    ns[i]=s[i]
pos=0
cache=list()
res=''

while len(res)<n:
    c,i=mi[pos]
    res+=c
    cache+=ns[pos:i]
    pos=i
    if  cache:
        val =cache[-1]
        mi[pos]=(val,pos)
        ns[pos]=val
        if pos<n-1:
            mi[pos]=min(mi[pos],mi[pos+1])
        cache.pop()
    else:
        pos+=1
        
        
print( res   ) 


s = input()
prefmin = ['{'] * (len(s) + 1)
st = []

for i in range(len(s) - 1, -1, -1):
    prefmin[i] = min(s[i], prefmin[i + 1])

for i in range(len(s)):
    while len(st) and st[-1] <= prefmin[i]:
        print(st.pop(), end='')
    if prefmin[i] == s[i]:
        print(s[i], end='')
    else:
        st.append(s[i])

for i in range(len(st) - 1, -1, -1):
    print(st[i], end='')



def main():
    s = list(input())

    suffix = []
    for x in reversed(s):
        if suffix:
            suffix.append(min(suffix[-1], x))
        else:
            suffix.append(x)

    suffix = suffix[::-1]

    u = []
    t = []
    i = 0

    while True:
        m = suffix[i]

        while t and t[-1] <= m:
            u.append(t[-1])
            t.pop()

        while s[i] != m:
            t.append(s[i])
            i += 1

        u.append(s[i])

        i += 1
        if i == len(s):
            break

    u += t[::-1]

    print(''.join(u))


main()


def main():
    s = list(input())

    suffix = []
    for x in reversed(s):
        if suffix:
            suffix.append(min(suffix[-1], x))
        else:
            suffix.append(x)

    suffix = suffix[::-1]

    u = []
    t = []
    i = 0

    while True:
        m = suffix[i]

        while t and t[-1] <= m:
            u.append(t[-1])
            t.pop()

        while s[i] != m:
            t.append(s[i])
            i += 1

        u.append(s[i])

        i += 1
        if i == len(s):
            break

    u += t[::-1]

    print(''.join(u))


main()


#!/usr/bin/pypy3

# s[0] -> t[-1] or t[-1]->u[-1]
# "cab" ->("cab","","")->("ab","c","")->("b","ca","")->("b","c","a")
# 1) stack s->t until min(s).
# 2) passthrough min(s)->u
# min(s,t[-1]) -> u. Repeat.
# need to know the smallest item in s (quickly)
# think it's: split into two subsequences, merge s1(reverse)+s2. minimum.
# "cab" -> s1="cb",s2="a" -> bc
# "dcab" -> "b","dca"
from sys import stdin,stderr

def readInts(): return map(int,stdin.readline().strip().split())
def print_err(*args,**kwargs): print(*args,file=stderr,**kwargs)
    
def solve(s):
    s = list(s)
    sn = len(s)
    pq = sorted(zip(list(s),range(sn)))
    ix_left = 0
    u,v = [],[]
    for c,ix in pq:
        if ix < ix_left: continue
        while u and c >= u[-1]: v.append(u.pop())
        for cix in range(ix_left,ix+1): u.append(s[cix])
        ix_left = ix+1
    while u: v.append(u.pop())
    return v    

def run():
    s = input().strip()
    print("".join(solve(s)))
        
run()


s=input()
c=[0]*26
for i in s:
    c[ord(i)-97]+=1
t=[]
u=[]
for i in s:
    t.append(i)
    c[ord(i)-97]-=1
    while t and sum(c[:(ord(t[-1])-97)])==0:
        u.append(t.pop())
        
print(''.join(u))