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: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
ptr = ord('a')

def s_has_smaller(s_cnt_local, c):
	global 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:
	if not s:
		while t:
			u.append(t.pop())
	elif not t:
		x = s.pop()
		s_cnt[ord(x)] -= 1
		t.append(x)
	elif 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))


ct = [0] * 26
string = input()
for s in string:
	ct[ord(s) - ord('a')] += 1
t = []
u = []
for s in string:
	t.append(s)
	ct[ord(s) - ord('a')] -= 1
	while t and sum(ct[:ord(t[-1]) - ord('a')]) == 0:
		u.append(t.pop())
print(*u, sep='')


s = input()
ls = len(s)
s1 = s[::-1]
d = dict()
t = list()
u = list()
sets = sorted(set(s))
setsl = len(sets)
for i in range(setsl):
	try:
		idx = s1.index(sets[i])
		if i == 0:
			d[sets[i]] = (0, ls - idx - 1)
			prev = sets[i]
		elif ls - idx - 1 > d[prev][1]:
			d[sets[i]] = (d[prev][1] + 1, ls - idx - 1)
			prev = sets[i]
	except:
		pass
for i in d:
	while t and t[-1] <= i:
		u.append(t.pop())
	for j in range(d[i][0], d[i][1] + 1):
		if s[j] == i:
			u.append(s[j])
		else:
			t.append(s[j])
u = ''.join(u + t[::-1])
print(u)


def place(c):
	return ord(c) - ord('a')
(s, stk, res, freq) = (input(), [], [], [0 for i in range(26)])
for c in s:
	freq[place(c)] += 1
for c in s:
	(freq[place(c)], isLowAvailable, _) = (freq[place(c)] - 1, False, stk.append(c))
	while stk and (not isLowAvailable):
		for i in range(place(stk[-1]) - 1, -1, -1):
			if freq[i]:
				isLowAvailable = True
		if not isLowAvailable:
			res.append(stk.pop())
while stk:
	res.append(stk.pop())
print(''.join(res))


from collections import OrderedDict

def getMinAlpha(freq):
	for i in freq:
		if freq[i] != 0:
			break
	return i
s = input()
(t, u) = ([], [])
freq = OrderedDict()
for i in range(1, 27):
	freq.update({chr(i + 96): 0})
for i in range(len(s)):
	freq.update({s[i]: freq[s[i]] + 1})
for i in range(len(s)):
	minElm = getMinAlpha(freq)
	while len(t) > 0 and t[-1] <= minElm:
		u.append(t.pop())
	if s[i] == minElm:
		u.append(s[i])
	else:
		t.append(s[i])
	freq.update({s[i]: freq[s[i]] - 1})
while len(t) > 0:
	u.append(t.pop())
print(''.join(u))


s = input()
t = list()
ans = ''
index = 0
for character in 'abcdefghijklmnopqrstuvwxyz':
	while len(t) > 0 and t[-1] <= character:
		ans += t[-1]
		t.pop()
	pos = s.find(character, index)
	while pos >= 0:
		while index < pos:
			t.append(s[index])
			index += 1
		ans += character
		index += 1
		pos = s.find(character, index)
while len(t) > 0:
	ans += t[-1]
	t.pop()
print(ans)


s = input()
n = len(s)
freq = [0] * 26
if len(s) == 0:
	print('')
for i in s:
	freq[ord(i) - ord('a')] += 1
stack = []
ans = ''
for i in range(n):
	stack.append(s[i])
	freq[ord(s[i]) - ord('a')] -= 1
	flag = True
	while len(stack) and flag:
		for j in reversed(range(ord(stack[-1]) - ord('a'))):
			if freq[j] > 0:
				flag = False
		if flag:
			ans += stack[-1]
			stack.pop()
print(ans)


from sys import stdin, stdout
from collections import deque
sze = 26
s = stdin.readline().strip()
second = []
third = []
position = [-1 for i in range(sze)]
for i in range(len(s)):
	position[ord(s[i]) - ord('a')] = i
i = 0
for k in range(sze):
	if position[k] == -1:
		continue
	while second and ord(second[-1]) - ord('a') <= k:
		third.append(second.pop())
	while i <= position[k]:
		if ord(s[i]) - ord('a') == k:
			third.append(s[i])
		else:
			second.append(s[i])
		i += 1
third.extend(second[::-1])
stdout.write(''.join(third))


s = input()
t = []
u = []
n = len(s)
a = [0] * 26
for i in range(len(s)):
	z = ord(s[i]) - 97
	a[z] += 1
FirstLetterInS = 0
LengthT = 0
while len(u) != n:
	if len(t) == 0:
		a[ord(s[FirstLetterInS]) - 97] -= 1
		z = s[FirstLetterInS]
		t.append(z)
		FirstLetterInS += 1
	else:
		flag = False
		x = -1
		for i in range(ord(t[-1]) - 97):
			if a[i] > 0:
				flag = True
				break
		if flag:
			z = s[FirstLetterInS]
			t.append(z)
			FirstLetterInS += 1
			a[ord(z) - 97] -= 1
		else:
			u += t[-1]
			t.pop()
print(''.join(u))


ct = [0] * 26
string = input().strip()
for i in string:
	ct[ord(i) - ord('a')] += 1
(t, u) = ([], [])
for i in string:
	t.append(i)
	ct[ord(i) - ord('a')] -= 1
	while t and sum(ct[:ord(t[-1]) - ord('a')]) == 0:
		u.append(t.pop())
print(''.join(u))


import math
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def hasGreater(c):
	global mp
	for (k, v) in mp.items():
		if c > k and v:
			return True
	return False
s = [v for v in input()]
t = []
ans = ''
n = len(s)
mp = {chr(ord('a') + i): 0 for i in range(26)}
for v in s:
	mp[v] += 1
for v in s:
	if len(t):
		while len(t) and (not hasGreater(t[-1])):
			ans += t.pop()
	t.append(v)
	mp[v] -= 1
while len(t):
	ans += t.pop()
print(ans)


from collections import defaultdict

def check(c):
	global freq
	for val in freq:
		if freq[val] > 0:
			if ord(c) > ord(val):
				return False
	return True
freq = defaultdict(int)
s = input().strip()
for i in s:
	freq[i] += 1
stack = []
res = ''
for i in s:
	stack.append(i)
	freq[i] -= 1
	while stack and check(stack[-1]):
		f = 1
		res += stack.pop()
while stack:
	res += stack.pop()
print(res)


s = input()
n = []
for i in range(len(s)):
	n.append('z')
n[-1] = s[-1]
a = s[-1]
for i in range(len(s) - 2, -1, -1):
	if a > s[i]:
		a = s[i]
	n[i] = a
index = n.index(min(n))
q = []
u = ''
for i in range(len(s)):
	while q and q[-1] <= n[i]:
		u += q.pop()
	q.append(s[i])
print(u + ''.join(map(str, q[::-1])))


from sys import stdin
(lines, line_index) = (stdin.readlines(), -1)

def get_line():
	global lines, line_index
	line_index += 1
	return lines[line_index]

def next_min_char(info):
	for (k, v) in enumerate(info):
		if v != 0:
			return k
	return -1

def main():
	data = get_line().strip()
	stack = []
	output = []
	a = ord('a')
	z = a + 26
	n = len(data)
	best = [-1] * (n + 1)
	best[n] = z
	for i in range(n - 1, -1, -1):
		best[i] = min(best[i + 1], ord(data[i]))
	cur = 0
	while stack or cur < n:
		if stack and ord(stack[-1]) <= best[cur]:
			output.append(stack.pop())
		else:
			stack.append(data[cur])
			cur += 1
	print(''.join(output))
main()


import sys
import math
import collections
import heapq
s = input()
n = len(s)
freq = [0] * 27
for i in range(n):
	freq[ord(s[i]) + 1 - 97] += 1
for i in range(1, 27):
	freq[i] += freq[i - 1]
(u, t) = ([], [])
for i in range(n):
	t.append(s[i])
	for i in range(ord(s[i]) - 97 + 1, 27):
		freq[i] -= 1
	while len(t) > 0 and freq[ord(t[-1]) - 97] < 1:
		u.append(t.pop())
print(''.join(u))


s = list(input())
t = []
u = ''
alphabets = list('abcdefghijklmnopqrstuvwxyz')
idx = 0
for c in alphabets:
	while t and t[-1] <= c:
		u = u + t.pop()
	try:
		nxt = s.index(c, idx)
	except ValueError:
		nxt = -1
	while nxt >= 0:
		while idx < nxt:
			t.append(s[idx])
			idx += 1
		u = u + c
		idx += 1
		try:
			nxt = s.index(c, idx)
		except ValueError:
			nxt = -1
while t:
	u = u + t.pop()
print(u)


s = input()

def f(l=0):
	c = min(s[l:])
	cnt = s[l:].count(c)
	return (c, cnt)
(c, cnt) = f()
(res, t) = ([], [])
for (i, e) in enumerate(s):
	if e == c:
		res.append(e)
		if cnt > 1:
			cnt -= 1
		else:
			if i == len(s) - 1:
				break
			(c, cnt) = f(i + 1)
			while len(t) and t[-1] <= c:
				res.append(t[-1])
				t.pop()
	else:
		t.append(e)
print(''.join(res + t[::-1]))


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
s = input()
n = len(s)
minAfter = [-1] * n
minAfter[n - 1] = 0
mi = n - 1
for i in range(n - 2, -1, -1):
	minAfter[i] = mi
	if s[i] <= s[mi]:
		mi = i
key = s.index(min(s))
st = []
ans = []
for i in range(n):
	if i == key:
		ans.append(s[i])
		key = minAfter[i]
		while len(st) and key and (st[-1] <= s[key]):
			ans.append(st.pop())
	else:
		st.append(s[i])
ans += st[::-1]
print(*ans, sep='')


base = ord('a')
char_list = [ord(char) - base for char in list(input())]
min_string = ''
char_count = [0] * 26
stack = []
for x in char_list:
	char_count[x] += 1
cur_min_char = 0
for i in range(26):
	if char_count[i]:
		cur_min_char = i
		break
for x in char_list:
	if x == cur_min_char:
		min_string += chr(x + base)
		char_count[x] -= 1
		if char_count[x] == 0:
			cur_min_char = 0
			for i in range(26):
				if char_count[i]:
					cur_min_char = i
					break
			while stack and stack[-1] <= cur_min_char:
				min_string += chr(stack.pop() + base)
	else:
		stack.append(x)
		char_count[x] -= 1
while stack:
	min_string += chr(stack.pop() + base)
print(min_string)


s = list(input())
t = []
u = []
letters = [[] for _ in range(ord('z') - ord('a') + 1)]
for (index, letter) in enumerate(s):
	letters[ord(letter) - ord('a')] += [index]
for indexes in letters:
	indexes.reverse()
current = 0
while current < len(s):
	if len(t) == 0:
		t += s[current]
		letters[ord(s[current]) - ord('a')].pop()
		current += 1
		continue
	best_in_word = chr(ord('z') + 1)
	best_index = -1
	for i in range(ord('z') - ord('a') + 1):
		if len(letters[i]) != 0:
			best_in_word = chr(ord('a') + i)
			best_index = letters[i][-1]
			break
	if t[-1] <= best_in_word:
		u += t[-1]
		t.pop()
		continue
	while current <= best_index:
		t += s[current]
		letters[ord(s[current]) - ord('a')].pop()
		current += 1
while len(t) > 0:
	u += t[-1]
	t.pop()
print(''.join(u))


s = input()
n = len(s)
freq = [0] * 27
for i in range(n):
	freq[ord(s[i]) + 1 - 97] += 1
for i in range(1, 27):
	freq[i] += freq[i - 1]
(u, t) = ([], [])
for i in range(n):
	t.append(s[i])
	for i in range(ord(s[i]) - 97 + 1, 27):
		freq[i] -= 1
	while len(t) > 0 and freq[ord(t[-1]) - 97] < 1:
		u.append(t.pop())
print(''.join(u))


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()


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()


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 collections import deque
s = list(input())
s_deque = deque(s)
ch_cnt = {}
for ch in s:
	if ch not in ch_cnt:
		ch_cnt[ch] = 0
	ch_cnt[ch] += 1
t = []
u = ''
while s_deque:
	ch = s_deque.popleft()
	while t and all((t[-1] <= i for i in ch_cnt)):
		tmp_ch = t.pop()
		u += tmp_ch
	t.append(ch)
	ch_cnt[ch] -= 1
	if ch_cnt[ch] == 0:
		del ch_cnt[ch]
while t:
	tmp_ch = t.pop()
	u += tmp_ch
print(u)


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


s = input()
min_s = [chr(123)] * len(s)
min_s[-1] = s[-1]
for i in range(len(s) - 2, -1, -1):
	min_s[i] = min(s[i], min_s[i + 1])
t = []
u = []
for i in range(len(s)):
	if len(t) and min_s[i] >= t[-1]:
		while len(t) and t[-1] <= min_s[i]:
			u.append(t.pop())
	if s[i] == min_s[i]:
		u.append(s[i])
	else:
		t.append(s[i])
u = u + t[::-1]
assert len(u) == len(s)
print(''.join(u))


input_str = input()
s = []
t = []
u = []
for x in input_str:
	s.append(x)
s.reverse()
var = 97
while len(s) != 0 or len(t) != 0:
	track = len(s)
	for z in range(len(s) - 1, -1, -1):
		if s[z] == chr(var):
			track = z
			for y in range(len(s) - 1, z, -1):
				t.append(s[y])
				s.pop()
			u.append(s[z])
			s.pop()
	var += 1
	while True:
		if len(t) != 0 and ord(t[len(t) - 1]) <= var:
			u.append(t[len(t) - 1])
			t.pop()
		else:
			break
output_str = ''
for z in u:
	output_str += z
print(output_str)


def find_min(count):
	for i in range(26):
		if count[i] > 0:
			return i
	return -1

def calc_pos(letter):
	return ord(letter) - ord('a')
s = input()
count = [0 for i in range(26)]
for c in s:
	count[calc_pos(c)] += 1
t = []
u = ''
for i in range(len(s)):
	t.append(s[i])
	count[calc_pos(s[i])] -= 1
	while t and find_min(count) != -1 and (calc_pos(t[-1]) <= find_min(count)):
		u += t.pop()
while len(t) > 0:
	u += t.pop()
print(u)


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]):
			u.append(t.pop())
		else:
			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}
	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]):
			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:
				continue
			elif min_idx == curr_idx:
				if len(t) > 0 and ord(char) > ord(t[-1]):
					raise Exception()
				u.append(char)
				curr_idx += 1
				continue
			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
import string
s = input()
u = []
t = []
efficient_sol()
print(''.join(u + list(reversed(t))))


s = input()
al = [0] * 27
for e in s:
	al[ord(e) - 96] += 1
t = []
ans = ''
for e in range(len(s)):
	t.append(s[e])
	al[ord(s[e]) - 96] -= 1
	while e < len(s) - 1 and t and (sum(al[:ord(t[-1]) - 96]) == 0):
		ans += t[-1]
		t.pop()
while t:
	ans += t[-1]
	t.pop()
print(ans)


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))


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()))


import random, math, sys
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right
from collections import Counter
input = sys.stdin.readline

def solution(s):
	a = []
	b = []
	indi = 0
	se = Counter(list(s))
	se1 = {}
	for i in list(s):
		if i == min(se.keys()):
			b.append(i)
		else:
			a.append(i)
			se1[i] = se1.get(i, 0) + 1
		se[i] -= 1
		if se[i] == 0:
			del se[i]
		while a and len(se) and (a[-1] <= min(se.keys())):
			b.append(a.pop())
	while a:
		b.append(a.pop())
	return ''.join(b)

def input_test():
	s = input().strip()
	out = solution(s)
	print(out)

def test():
	pass
input_test()


import sys
from collections import defaultdict
s = list(sys.stdin.readline().strip())

def min_char(char2count):
	alphabet = 'abcdefghijklmnopkrstuvwxyz'
	for char in alphabet:
		if char2count[char] > 0:
			return char
char2count = defaultdict(int)
for char in s:
	char2count[char] += 1
(t, u) = ([], [])
minc = min_char(char2count)
while len(s) > 0:
	if len(t) == 0:
		char = s.pop(0)
		t.append(char)
		char2count[char] -= 1
		if char2count[char] == 0:
			minc = min_char(char2count)
	elif t[-1] <= minc:
		u.append(t.pop())
	else:
		char = s.pop(0)
		t.append(char)
		char2count[char] -= 1
		if char2count[char] == 0:
			minc = min_char(char2count)
while len(t) > 0:
	u.append(t.pop())
print(''.join(u))


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])


import sys
s = input()
n = len(s)
smallest = [''] * (n - 1) + [s[-1]]
for i in range(n - 2, -1, -1):
	smallest[i] = min(smallest[i + 1], s[i])
(t, u) = ([], [])
for i in range(n):
	while t and t[-1] <= smallest[i]:
		u.append(t.pop())
	if s[i] == smallest[i]:
		u.append(s[i])
	else:
		t.append(s[i])
u += t[::-1]
print(*u, sep='')


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
str1 = ''.join(ans)
print(str1)


s = input()
l = len(s)
mn = [0] * l
mnn = s[-1]
for i in range(l - 1, -1, -1):
	mnn = min(mnn, s[i])
	mn[i] = mnn
st = []
for i in range(0, l):
	while len(st) != 0 and st[-1] <= mn[i]:
		print(st.pop(), end='')
	st.append(s[i])
while len(st) != 0:
	print(st.pop(), end='')


import string

def solve(s):
	alpha = {x: i for (i, x) in enumerate(list(string.ascii_lowercase))}
	(t, u) = ([], [])
	s = list(s)[::-1]
	char_count = [0] * 26
	for char in s:
		char_count[alpha[char]] += 1
	while s:
		char = s.pop()
		t.append(char)
		char_count[alpha[char]] -= 1
		m = min([float('inf')] + [i for (i, x) in enumerate(char_count) if x])
		while t and m >= alpha[t[-1]]:
			u.append(t.pop())
	while t:
		u.append(t.pop())
	return ''.join(u)
print(solve(input()))


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='')


s = input()
c = ['z'] * (len(s) + 1)
for i in range(len(s) - 1, -1, -1):
	c[i] = min(c[i + 1], s[i])
st = list()
i = 0
while len(st) > 0 or i < len(s):
	if len(st) > 0 and st[len(st) - 1] <= c[i]:
		print(st[len(st) - 1], end='')
		st.pop()
	else:
		st.append(s[i])
		i += 1
print()


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])
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 compare(a, vis):
	for i in range(0, ord(a) - ord('a')):
		if vis[i] > 0:
			return False
	return True
n = input()
vis = [0] * 26
for letter in n:
	vis[ord(letter) - ord('a')] = vis[ord(letter) - ord('a')] + 1
st = []
s = []
for i in range(0, len(n)):
	st.append(n[i])
	vis[ord(n[i]) - ord('a')] = vis[ord(n[i]) - ord('a')] - 1
	while len(st) > 0 and compare(st[len(st) - 1], vis):
		s.append(st[len(st) - 1])
		st.pop()
while len(st) != 0:
	s.append(st[len(st) - 1])
	st.pop()
for letter in s:
	print(letter, end='')


s = input()
dic = {}
t = []
u = ''
for i in s:
	if i in dic:
		dic[i] = dic[i] + 1
	else:
		dic[i] = 1
j = 'a'
for i in s:
	while j not in dic or dic[j] == 0:
		j = chr(ord(j) + 1)
	if len(t) > 0:
		last_t = t[-1]
		while ord(j) >= ord(last_t):
			u = u + last_t
			t.pop()
			if len(t) == 0:
				break
			last_t = t[-1]
	t.append(i)
	dic[i] = dic[i] - 1
len_t = len(t)
for i in range(len_t):
	u = u + t.pop()
print(u)


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])))


s = input()
leng = len(s)
minarray = [0] * leng
mins = 'z'
for i in range(leng - 1, -1, -1):
	if s[i] < mins:
		mins = s[i]
	minarray[i] = mins
st = []
fist = []
for i in range(leng):
	while st != [] and st[-1] <= minarray[i]:
		fist.append(st[-1])
		st.pop()
	if s[i] == minarray[i]:
		fist.append(s[i])
	else:
		st.append(s[i])
while st != []:
	fist.append(st[-1])
	st.pop()
print(''.join(fist))


def findout(s):
	from collections import defaultdict
	dic = defaultdict(list)
	for i in range(len(s)):
		dic[s[i]] += [i]
	possible = sorted([x for x in dic])
	stack = []
	index = -1
	checked = [0] * len(s)
	for x in possible:
		stop = dic[x][-1]
		if stop < index:
			continue
		if stack:
			while ord(stack[-1]) <= ord(x):
				print(stack.pop(), end='')
				if not stack:
					break
		for i in range(index + 1, stop + 1):
			if s[i] != x:
				stack += [s[i]]
			elif checked[i] == 0:
				checked[i] = 1
				print(s[i], end='')
		index = stop
	while stack:
		print(stack.pop(), end='')
findout(input())


s = list(input())
s.reverse()
n = len(s)
min_char = [s[0]]
for i in range(1, n):
	min_char.append(min(s[i], min_char[i - 1]))
t = []
u = []
while len(u) < n:
	if len(t) == 0:
		t.append(s.pop())
	elif len(s) == 0:
		u.append(t.pop())
	elif min_char[len(s) - 1] < t[-1]:
		t.append(s.pop())
	else:
		u.append(t.pop())
print(''.join(u))


from collections import Counter
s = input()
t = []
u = []
s = list(s)
cc = dict(Counter(s))
f = sorted(list(set(s)))
ch = f[0]
k = 0
for i in range(len(s)):
	t.append(s[i])
	cc[s[i]] -= 1
	while cc[ch] == 0:
		k += 1
		try:
			ch = f[k]
		except:
			break
	while t[-1] <= ch:
		gg = t.pop()
		u.append(gg)
		if not t:
			break
while t:
	gg = t.pop()
	u.append(gg)
print(''.join(u))


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a * a + b * b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
s = list(input())
ans = []
n = len(s)
st = 0
sw = SegmentTree1(s)
t = []
while len(ans) < n:
	if st == n:
		break
	re = sw.query(st, n - 1)
	cou = -1
	while True:
		if len(t) == 0:
			break
		if t[cou] <= re:
			ans += t[cou]
			t.pop()
		else:
			break
	while True:
		if s[st] == re:
			ans += re
			st += 1
			break
		else:
			t.append(s[st])
			st += 1
if len(t) > 0:
	for i in range(len(t) - 1, -1, -1):
		ans += t[i]
print(*ans, sep='')


from collections import deque
s = deque(input())
t = deque()
u = ''
alphabet = list('abcdefghijklmnopqrstuvxwyz')
dic = {k: i for (i, k) in enumerate(alphabet)}
c = [0 for l in alphabet]
for l in s:
	c[dic[l]] += 1
j = 0
while len(s) > 0:
	curr = s[0]
	desired = alphabet[j]
	flag = False
	while len(t) > 0 and t[-1] <= desired:
		flag = True
		u += t.pop()
	if not c[j] and j < len(c) - 1:
		j += 1
		continue
	while len(s) > 0 and s[0] == desired:
		flag = True
		c[j] -= 1
		u += s.popleft()
	if not flag:
		c[dic[curr]] -= 1
		t.append(s.popleft())
while len(t) > 0:
	u += t.pop()
print(u)


restantes = {}

def possui_menor(l):
	n = ord(l) - ord('a')
	for k in sorted(restantes.keys()):
		if k >= l:
			break
		if restantes[k] > 0:
			return True
	return False
s = list(input())
pilha = []
resposta = ''
for l in s:
	if l not in restantes:
		restantes[l] = 0
	restantes[l] += 1
for l in s:
	pilha.append(l)
	restantes[l] = restantes[l] - 1
	prox = pilha[-1]
	while len(pilha) > 0 and (not possui_menor(prox)):
		resposta += pilha.pop(-1)
		if len(pilha) > 0:
			prox = pilha[-1]
while len(pilha) > 0:
	resposta += pilha.pop(-1)
print(resposta)


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))


RI = lambda : [int(x) for x in input().split()]
rw = lambda : [input().strip()]
s = list(input().strip())
stack = []
index_stack = -1
ans = ''
d = {}
ch = 'abcdefghijklmnopqrstuvwxyz'
for i in ch:
	d[i] = 0
for i in range(len(s)):
	d[s[i]] += 1
previous = -1
index = 0
for i in d:
	while index_stack >= 0 and stack[index_stack] <= i:
		ans += stack[index_stack]
		stack.pop()
		index_stack -= 1
	while index != len(s) and d[i] != 0:
		if s[index] == i:
			ans += i
			d[i] -= 1
		else:
			stack.append(s[index])
			index_stack += 1
			d[s[index]] -= 1
		index += 1
while len(stack) != 0:
	ans += stack[index_stack]
	index_stack -= 1
	stack.pop()
print(ans)


def getindex(a):
	return ord(a) - 97
s = input()
cs = [0 for i in range(26)]
t = []
u = []
for i in s:
	cs[getindex(i)] += 1
ls = 0
for i in range(len(s)):
	si = getindex(s[i])
	while cs[ls] == 0:
		ls += 1
	while t and getindex(t[-1]) <= ls:
		u.append(t.pop())
	if ls != si:
		t.append(s[i])
	else:
		u.append(s[i])
	cs[si] -= 1
while t:
	u.append(t.pop())
print(''.join(u))


import sys
import heapq

def get_string():
	return sys.stdin.readline().strip()

def solve(s):
	length = len(s)
	current = 97
	final = []
	start = 0
	end = length - 1
	extra = []
	while start <= end and current <= 122:
		ele = chr(current)
		temp = end
		flag = 0
		while extra:
			if extra[-1] <= ele:
				final.append(extra[-1])
				extra.pop()
			else:
				break
		while temp >= start:
			if s[temp] <= ele:
				flag = 1
				break
			else:
				temp -= 1
		if flag == 1:
			for i in range(start, temp + 1):
				if s[i] <= ele:
					final.append(s[i])
				else:
					extra.append(s[i])
			start = temp + 1
			end = length - 1
		current += 1
	extra.reverse()
	final.extend(extra)
	sys.stdout.write(''.join(map(str, final)) + '\n')
	return
s = get_string()
solve(s)


from sys import stdin
from collections import deque
input = stdin.readline
s = input().strip()
t = []
u = []
x = deque()
cur_min = 'z'
for i in range(len(s) - 1, -1, -1):
	cur_min = min(cur_min, s[i])
	x.appendleft(cur_min)
i = 0
while i < len(s):
	if len(t) > 0 and t[-1] <= x[i]:
		u.append(t.pop())
	else:
		target = x[i]
		while s[i] != target:
			t.append(s[i])
			i += 1
		t.append(s[i])
		i += 1
while t:
	u.append(t.pop())
print(*u, sep='')


s = list(map(ord, list(input())))
n = len(s)
t = []
u = ''
arr = [0] * 26
for i in s:
	arr[i - 97] += 1
for i in s:
	arr[i - 97] -= 1
	t.append(chr(i))
	while t and sum(arr[:ord(t[-1]) - 97]) == 0:
		u += t.pop()
while t:
	u += t.pop()
print(u)


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)
	elif 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()
u = ''
t = []
d1 = [0] * 26
d2 = [0] * 26
n = len(s)
a = ord('a')
for i in range(n):
	d1[ord(s[i]) - a] += 1
i = 0
for j in range(26):
	while i < n and d2[j] < d1[j]:
		if s[i] == chr(j + a):
			u += s[i]
			d2[j] += 1
		else:
			t.append(s[i])
			d2[ord(s[i]) - a] += 1
		i += 1
	for p in range(26):
		if d2[p] < d1[p]:
			q = p
			break
	else:
		q = 26
	while len(t) > 0 and t[-1] <= chr(q + a):
		k = t.pop(-1)
		u += k
print(u)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq
from collections import Counter
s = input()
d = [0] * 26
t = []
ans = []
for i in s:
	d[ord(i) - 97] += 1
for i in s:
	t.append(i)
	d[ord(i) - 97] -= 1
	while t and sum(d[:ord(t[-1]) - 97]) == 0:
		ans.append(t.pop())
print(''.join(ans))


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
s = list(ip())
suf = ['z' for i in range(len(s) + 2)]
suf[len(s) - 1] = s[len(s) - 1]
for i in range(len(s) - 1, 0, -1):
	suf[i - 1] = min(s[i - 1], suf[i])
ans = []
x = suf[0]
b = []
i = 0
while i < len(s) or len(b) > 0:
	if len(b) > 0 and b[len(b) - 1] <= suf[i]:
		ans.append(b[len(b) - 1])
		b.pop()
	else:
		b.append(s[i])
		i += 1
print(''.join(ans))


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)


def solve(s):
	suffix_min = []
	t = []
	u = []
	m = 'z'
	for c in reversed(s):
		m = min(m, c)
		suffix_min.append(m)
	for (c, m) in zip(s, reversed(suffix_min)):
		while len(t) > 0:
			top = t.pop()
			if top <= m:
				u.append(top)
			else:
				t.append(top)
				break
		if c > m:
			t.append(c)
		else:
			u.append(c)
	return ''.join(u) + ''.join(reversed(t))

def main():
	print(solve(input()))
main()


(sequence, stack, letter_count, ans) = (input(), [], [0] * 26, '')
for x in sequence:
	letter_count[ord(x) - 97] += 1
for x in sequence:
	stack.append(x)
	letter_count[ord(x) - 97] -= 1
	while stack and sum(letter_count[:ord(stack[-1]) - 97]) == 0:
		ans += stack.pop()
print(ans)


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0

def hnbhai(tc):
	s = list(sa())
	if s == list(sorted(s)):
		print(''.join(s))
		return
	freq = [0] * 26
	for i in s:
		freq[ord(i) - ord('a')] += 1
	t = []
	u = []
	for i in s:
		t.append(i)
		x = ord(i) - ord('a')
		freq[x] -= 1
		while t and sum(freq[:ord(t[-1]) - ord('a')]) == 0:
			u.append(t.pop())
	print(''.join(u))
for _ in range(1):
	hnbhai(_ + 1)


s = input()
n = len(s)
mins = [ord('z') + 1] * n
mins[-1] = s[-1]
for i in range(1, n):
	mins[-i - 1] = min(mins[-i], s[-i - 1])
a = []
r = ''
i = 0
j = 0
while i < n:
	while len(a) > 0 and a[-1] <= mins[i]:
		r += a.pop()
	mn = mins[i]
	while s[i] > mn:
		a.append(s[i])
		i += 1
	a.append(s[i])
	i += 1
while len(a) > 0:
	r += a.pop()
print(r)


s = input()
s = s[-1::-1]
l = [s[0]]
for i in range(1, len(s)):
	l.append(min(s[i], l[-1]))
s = s[-1::-1]
l = l[-1::-1]
st = []
p1 = 0
ans = []
while len(ans) != len(s):
	if p1 + 1 < len(l) and l[p1 + 1] < s[p1]:
		if len(st) != 0 and l[p1 + 1] >= st[-1]:
			ans.append(st[-1])
			st.__delitem__(len(st) - 1)
		else:
			st.append(s[p1])
			p1 += 1
	elif len(st) == 0:
		ans.append(s[p1])
		p1 += 1
	elif p1 == len(l):
		ans.append(st[-1])
		st.__delitem__(len(st) - 1)
	elif s[p1] < st[-1]:
		ans.append(s[p1])
		p1 += 1
	else:
		ans.append(st[-1])
		st.__delitem__(len(st) - 1)
print(*ans, sep='')


s = [char for char in input().strip()]
alpha_dict = {}
for alpha in 'qwertyuiopasdfghjklzxcvbnm':
	alpha_dict[alpha] = 0
for char in s:
	alpha_dict[char] += 1
t = []
u = []
for char in s:
	t.append(char)
	alpha_dict[char] -= 1
	while t:
		top = t[-1]
		smaller_found = False
		for alpha in alpha_dict:
			if alpha < top and alpha_dict[alpha] > 0:
				smaller_found = True
				break
		if smaller_found:
			break
		else:
			u.append(t.pop())
while t:
	u.append(t.pop())
print(*u, sep='')


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


def go(cnt, n):
	for i in range(0, n):
		if cnt[i] > 0:
			return 1
	return 0
s = input()
n = len(s)
t = []
u = []
cnt = [0] * 26
for i in s:
	cnt[ord(i) - 97] += 1
for i in range(n):
	if len(t) == 0 or t[-1] >= s[i]:
		t.append(s[i])
	else:
		for j in reversed(t):
			if go(cnt, ord(j) - 97) == 0:
				u.append(j)
				t.pop()
			else:
				break
		t.append(s[i])
	cnt[ord(s[i]) - 97] -= 1
print(''.join(u + t[::-1]))


from collections import defaultdict
s = input()
n = len(s)
d = defaultdict(int)
for i in range(n):
	d[s[i]] += 1
stack = []
ans = ''
for i in range(n):
	stack.append(s[i])
	d[s[i]] -= 1
	ok = True
	while ok and stack:
		ok = False
		rem = True
		for j in range(ord('a'), ord(stack[-1])):
			char = chr(j)
			if d[char]:
				rem = False
				break
		if rem:
			ok = True
			ans += stack[-1]
			stack.pop()
print(ans)


s = input().strip()
t = []
u = []
a = 'abcdefghijklmnopqrstuvwxyz'
z = dict()
for i in a:
	z[i] = 0
for i in s:
	z[i] += 1
for i in s:
	t.append(i)
	z[i] -= 1
	while t:
		f = 0
		top = t[-1]
		for j in z:
			if j < top and z[j] > 0:
				f = 1
				break
		if f == 1:
			break
		else:
			u.append(t.pop())
while t:
	u.append(t.pop())
print(''.join(u))


import sys
import array
s = sys.stdin.readline().replace('\n', '')
n = len(s)
dp = array.array('i', range(n))
m = 'z'
for i in range(n - 1, -1, -1):
	m = min(m, s[i])
	dp[i] = ord(m)
t = ''
lt = 0
ans = ''
i = 0
while i < n:
	if lt != 0 and t[-1] <= chr(dp[i]):
		ans += t[-1]
		t = t[:lt - 1]
		lt -= 1
	elif s[i] == chr(dp[i]):
		ans += s[i]
		i += 1
	elif s[i] != chr(dp[i]):
		t += s[i]
		lt += 1
		i += 1
ans += t[::-1]
print(ans)


def fnz(l):
	for i in range(len(l)):
		if l[i] != 0:
			return i
	return i
alphabets = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
count_alph = [0] * 26
s = input()
t = []
u = []
for i in s:
	count_alph[alphabets.index(i)] += 1
for i in s:
	t.append(i)
	count_alph[alphabets.index(i)] -= 1
	while t[-1] <= alphabets[fnz(count_alph)]:
		u.append(t.pop())
		if len(t) == 0:
			break
u = u + t[::-1]
ans = ''
for i in u:
	ans += i
print(ans)


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()


ls = [0] * 26

def getFirst():
	for i in range(0, 26):
		if ls[i] > 0:
			return i

def remover(i):
	ls[i] -= 1
s = input()
c = {}
for i in s:
	n = ord(i) - 97
	if n in c:
		c[n] += 1
	else:
		c[n] = 1
ks = [*c]
for i in ks:
	ls[i] = c[i]
stack = []
ans = ''
i = int(0)
while i < len(s):
	f = getFirst()
	n = ord(s[i]) - 97
	if len(stack) != 0:
		if ord(stack[len(stack) - 1]) - 97 <= f:
			ans += stack.pop()
			i -= 1
		else:
			stack.append(s[i])
			remover(n)
	else:
		stack.append(s[i])
		remover(n)
	i += 1
while len(stack) > 0:
	a = stack.pop()
	ans += a
print(ans)


q_string = str(input())
l = len(q_string)
queue_list = [[0, 0] for i in range(l)]
for i in range(l):
	index = l - i - 1
	if index == l - 1:
		queue_list[index][0] = index
		queue_list[index][1] = q_string[index]
		continue
	elif queue_list[index + 1][1] < q_string[index]:
		queue_list[index][1] = queue_list[index + 1][1]
		queue_list[index][0] = queue_list[index + 1][0]
	else:
		queue_list[index][1] = q_string[index]
		queue_list[index][0] = index
s_stack = []
curr_index = 0
output_string = []
while len(output_string) != l:
	min_q = queue_list[curr_index][1]
	min_index_q = queue_list[curr_index][0]
	len_stack = len(s_stack)
	min_s = 'zz' if len_stack == 0 else s_stack[len_stack - 1]
	if min_q < min_s:
		for j in range(curr_index, min_index_q):
			s_stack.append(q_string[j])
		output_string.append(q_string[min_index_q])
		curr_index = min_index_q + 1
	else:
		output_string.append(s_stack[len_stack - 1])
		s_stack.pop()
	if curr_index >= l:
		while len(s_stack) != 0:
			output_string.append(s_stack.pop())
		break
print(''.join(output_string))


a = input()
b = list(a)
c = b[:]
c.sort()
t = []
answer = []
for i in range(len(c)):
	while len(t) != 0 and c[i] >= t[len(t) - 1]:
		answer.append(t[len(t) - 1])
		t.pop(len(t) - 1)
	if c[i] in b:
		if b[0] == c[i]:
			answer.append(b[0])
			b.pop(0)
		else:
			while b[0] != c[i]:
				t.append(b[0])
				b.pop(0)
			answer.append(b[0])
			b.pop(0)
if len(t) != 0:
	for i in range(1, len(t) + 1):
		answer.append(t[len(t) - i])
print(''.join(answer))


from collections import deque
s = deque(input())
t = []
u = []
ch = 'a'
while len(s) != 0:
	if ch in s:
		while len(t) > 0 and t[-1] <= ch:
			u.append(t.pop())
		n = s.count(ch)
		for _ in range(n):
			while s[0] != ch:
				t.append(s.popleft())
			u.append(s.popleft())
	ch = chr(ord(ch) + 1)
while len(t) != 0:
	u.append(t.pop())
print(''.join((x for x in u)))


from collections import defaultdict
s = list(input())
(t, u) = ([], [])
ds = defaultdict(int)
for c in s:
	ds[c] += 1
curr_alp_index = ord('a')
curr_pos_in_s = 0
while curr_alp_index <= ord('z'):
	curr_alp = chr(curr_alp_index)
	if len(t) > 0 and ord(t[-1]) <= ord(curr_alp):
		letter = t.pop()
		u.append(letter)
	elif ds[curr_alp] > 0:
		letter = s[curr_pos_in_s]
		curr_pos_in_s += 1
		t.append(letter)
		ds[letter] -= 1
	else:
		curr_alp_index += 1
t.reverse()
print(''.join(u + t))


import sys, math, queue
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
s = input()
s = list(s)
s = [ord(c) - 97 for c in s]
f = [0 for i in range(27)]
f[26] = 1
for c in s:
	f[c] += 1
ans = []
stack = []
j = 0
while f[j] == 0:
	j += 1
for c in s:
	stack.append(c)
	f[c] -= 1
	while f[j] == 0:
		j += 1
	while len(stack) > 0 and stack[-1] <= j:
		ans.append(stack.pop())
while len(stack) > 0:
	ans.append(stack.pop())
print(''.join([chr(i + 97) for i in ans]))


(s, t, u) = (input(), [], '')
(j, n) = (0, len(s))
p = ['|'] * (n + 1)
for i in range(n, 0, -1):
	p[i - 1] = min(s[i - 1], p[i])
while j < n:
	if t and t[-1] <= p[j]:
		u += t.pop()
	else:
		k = p[j]
		while p[j] == k:
			if s[j] == p[j]:
				u += s[j]
			else:
				t += [s[j]]
			j += 1
print(u + ''.join(t[::-1]))


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 lessnotpresent(each, d):
	for (key, value) in list(d.items()):
		if key < each and d[key] > 0:
			return False
	return True
from collections import defaultdict
s = list(input())
t = []
d = defaultdict(int)
u = []
for each in s:
	d[each] += 1
for each in s:
	t.append(each)
	d[each] -= 1
	while len(t) and lessnotpresent(t[-1], d):
		temp = t.pop()
		u.append(temp)
print(''.join(u + t[::-1]))


from collections import Counter, deque
S = input()
T = deque([])
ans = ''
cnt = Counter(S)
for (i, s) in enumerate(S):
	T.append(s)
	cnt[s] -= 1
	while T:
		smaller = 0
		tmp = T[-1]
		for key in cnt.keys():
			if key < tmp and cnt[key] > 0:
				smaller = 1
				break
		if smaller:
			break
		else:
			ans += T.pop()
print(ans)


str = list(input().strip())
alphabet = [0] * 26
t = []
u = []

def findFirst():
	for (index, val) in enumerate(alphabet):
		if val > 0:
			return index
	else:
		return False
i = 0
size = len(str)
while i < size:
	alphabet[ord(str[i]) - 97] += 1
	i += 1
i = 0
while i < size:
	t.append(str[i])
	count = 0
	while len(t):
		index = findFirst()
		alphabet[ord(t[-1]) - 97] -= 1
		val = chr(index + 97)
		if t[-1] == val:
			u.append(t.pop())
			if len(t):
				count += 1
				alphabet[ord(t[-1]) - 97] += 1
		else:
			break
	i += 1
while len(t):
	u.append(t.pop())
for item in u:
	print(item, end='')
print()


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
s = input()
a = [0] * 26
for i in range(0, len(s)):
	a[ord(s[i]) - 97] += 1
t = []
stack = []
ans = ''
for i in s:
	t.append(i)
	a[ord(i) - 97] -= 1
	while t and sum(a[:ord(t[-1]) - 97]) == 0:
		ans += t.pop()
print(ans)


s = input()
c = ['z'] * (len(s) + 1)
for i in range(len(s) - 1, -1, -1):
	c[i] = min(s[i], c[i + 1])
l = []
j = 0
while len(l) > 0 or j < len(s):
	if len(l) > 0 and l[len(l) - 1] <= c[j]:
		print(l[len(l) - 1], end='')
		l.pop()
	else:
		l.append(s[j])
		j += 1


def is_smallest(lst, pr, s):
	j = ord(s) - ord('a')
	for i in range(0, j):
		if lst[i] > 0:
			return False
	return True
inp_str = list(input())
res = ''
alpha = [0] * 26
qu = []
for i in range(0, len(inp_str)):
	j = ord(inp_str[i]) - ord('a')
	alpha[j] += 1
for x in inp_str:
	qu.append(x)
	k = ord(x) - ord('a')
	alpha[k] -= 1
	while is_smallest(alpha, qu, x):
		res += qu.pop()
		if not qu:
			break
		x = qu[-1]
while qu:
	res += qu.pop()
print(res)


import string

def get_min(a):
	for (ind, x) in enumerate(a):
		if x:
			return chr(ind + ord('a'))
	return None
s = input()
al = [s.count(x) for x in string.ascii_lowercase]
stack = []
i = 0
while i < len(s):
	if stack and stack[-1] <= get_min(al):
		print(stack.pop(), end='')
		continue
	stack.append(s[i])
	if s[i] == get_min(al):
		print(stack.pop(), end='')
	al[ord(s[i]) - ord('a')] -= 1
	i += 1
for i in stack[-1::-1]:
	print(i, end='')


s = input()

def get(i):
	m = min(s[i:])
	c = s[i:].count(m)
	return (m, c)
(m, c) = get(0)
(t, ans) = ([], [])
for (i, j) in enumerate(s):
	if j == m:
		ans.append(j)
		if c > 1:
			c -= 1
		elif i == len(s) - 1:
			break
		else:
			(m, c) = get(i + 1)
			while len(t) and t[-1] <= m:
				ans.append(t.pop())
	else:
		t.append(j)
print(''.join(ans + t[::-1]))


from string import ascii_lowercase
s = input()
cursor = 0
dct = dict.fromkeys(ascii_lowercase, 0)
for i in s:
	dct[i] += 1
fin = ''
curr = []
for j in dct.keys():
	while dct[j] != 0 and cursor != len(s):
		try:
			if ord(curr[-1]) <= ord(j):
				fin += curr[-1]
				curr.pop()
			else:
				if s[cursor] == j:
					fin += s[cursor]
				else:
					curr.append(s[cursor])
				dct[s[cursor]] -= 1
				cursor += 1
		except:
			if s[cursor] == j:
				fin += s[cursor]
			else:
				curr.append(s[cursor])
			dct[s[cursor]] -= 1
			cursor += 1
	if cursor == len(s):
		for k in range(len(curr) - 1, -1, -1):
			fin += curr[k]
		break
print(fin)


al = [0] * 26
bs = ord('a')
s = [ord(x) - bs for x in list(input())]
st = []
for x in s:
	al[x] += 1
cm = -1
for i in range(26):
	if al[i]:
		cm = i
		break
anso = []
for x in s:
	if x == cm:
		anso.append(x)
		al[cm] -= 1
		if not al[cm]:
			for i in range(cm, 26):
				if al[i]:
					cm = i
					break
			while st and st[-1] <= cm:
				anso.append(st.pop())
	else:
		al[x] -= 1
		st.append(x)
ans = ''
for x in anso:
	ans += chr(bs + x)
for x in st[::-1]:
	ans += chr(bs + x)
print(ans)


def get_min_char(freq):
	for c in 'abcdefghijklmnopqrstuvwxyz':
		if freq[c] != 0:
			return c

def solve(s):
	suffix_min = []
	t = []
	u = []
	letters = 'abcdefghijklmnopqrstuvwxyz'
	freq = {c: s.count(c) for c in letters}
	for c in s:
		m = get_min_char(freq)
		while len(t) > 0:
			top = t.pop()
			if top <= m:
				u.append(top)
			else:
				t.append(top)
				break
		if c > m:
			t.append(c)
		else:
			u.append(c)
		freq[c] -= 1
	return ''.join(u) + ''.join(reversed(t))

def main():
	print(solve(input()))
main()


s = list(input())
t = list()
u = list()
d = dict()
var = 97
for i in range(26):
	d[chr(var + i)] = 0
for i in s:
	d[i] += 1
i = 0
while i < len(s):
	if d[chr(var)] > 0:
		while i < len(s):
			d[s[i]] -= 1
			t.append(s[i])
			i += 1
			if t[-1] <= chr(var):
				u.append(t.pop())
				break
	else:
		var += 1
		while t and t[-1] <= chr(var):
			u.append(t.pop())
while t != []:
	u.append(t.pop())
print(''.join(u))


def have_less(x, ch):
	for k in range(ord(ch) - ord('a') - 1, -1, -1):
		if x[k] > 0:
			return True
	return False
s = input()
(t, u) = ([], [])
stat = [0] * 26
for ch in s:
	stat[ord(ch) - ord('a')] += 1
pos = 0
while pos < len(s):
	if len(t) == 0:
		stat[ord(s[pos]) - ord('a')] -= 1
		t.append(s[pos])
		pos += 1
	while pos < len(s) and have_less(stat, t[-1]):
		t.append(s[pos])
		stat[ord(s[pos]) - ord('a')] -= 1
		pos += 1
	u.append(t.pop())
print(''.join(u) + ''.join(t[::-1]))


s = list(input())
t = []
u = []
a = [[0 for i in range(26)]]
for i in range(len(s) - 1, -1, -1):
	b = a[-1][:]
	a.append(b)
	a[-1][ord(s[i]) - ord('a')] = a[-2][ord(s[i]) - ord('a')] + 1
b = a[::-1]
j = 0
i = 0
while i < len(s):
	if b[i][j] == 0:
		j += 1
		continue
	while len(t) > 0 and ord(t[-1]) <= j + ord('a'):
		u.append(t.pop())
	if b[i][j] != 0:
		if s[i] == chr(j + ord('a')):
			u.append(s[i])
		else:
			t.append(s[i])
	else:
		j += 1
	i += 1
while len(t) > 0:
	u.append(t.pop())
print(''.join(u))