Given a string, $\mbox{A}$, we define some operations on the string as follows:

a. $reverse(A)$ denotes the string obtained by reversing string $\mbox{A}$. Example: $\text{reverse()abc''})=\text{"cba''}$ 

b. $shuffle(A)$ denotes any string that's a permutation of string $\mbox{A}$. Example: $\textsf{shuffle("good^n)}\:\in\:\:['\textsf{good'},\:\:'\textsf{gdo'},\:\:\textsf{'cgd'},\:\:\textsf{'oddg'},\:\:\textsf{'dgo'},\:\:\textsf{'dog'}]$ 

c. $\textit{merge}(A1,A2)$ denotes any string that's obtained by interspersing the two strings $A\mathbf{1}$ & $A2$, maintaining the order of characters in both. For example, $\textbf{A1}=\textbf{"abc''}$ & $\textbf{A2}=\textbf{"def"}$, one possible result of $\textit{merge}(A1,A2)$ could be $\textbf{"abcdef"}$, another could be $\textbf{"abdef"}$, another could be $\textbf{"adbecf"}$ and so on.  

Given a string $\boldsymbol{\mathrm{~S~}}$ such that $\textbf{s}\in\textbf{merge(reverse(A)},\:\textbf{shuffle(A)})$ for some string $\mbox{A}$, find the lexicographically smallest $\mbox{A}$.

For example, $s=a b a b$.  We can split it into two strings of $\boldsymbol{ab}$.  The reverse is $\textbf{ba}$ and we need to find a string to shuffle in to get $\boldsymbol{abab}$.  The middle two characters match our reverse string, leaving the $\boldsymbol{\alpha}$ and $\boldsymbol{b}$ at the ends.  Our shuffle string needs to be $\boldsymbol{ab}$.  Lexicographically $ab<ba$, so our answer is $\boldsymbol{ab}$.  

Function Description

Complete the reverseShuffleMerge function in the editor below.  It must return the lexicographically smallest string fitting the criteria.  

reverseShuffleMerge has the following parameter(s):

s: a string

Input Format

A single line containing the string $\boldsymbol{\mathrm{~S~}}$.

Constraints

$\boldsymbol{\mathrm{~S~}}$ contains only lower-case English letters, ascii[a-z]  
$1\leq|s|\leq10000$  

Output Format

Find and return the string which is the lexicographically smallest valid $\mbox{A}$.

Sample Input 0
eggegg

Sample Output 0
egg

Explanation 0

Split "eggegg" into strings of like character counts: "egg", "egg" 

reverse("egg") = "gge" 

shuffle("egg") can be "egg" 

"eggegg" belongs to the merge of ("gge", "egg")

The merge is: $\boldsymbol{\mathrm{~e~}}$gge$\mbox{gg}$.

'egg' < 'gge'

Sample Input 1
abcdefgabcdefg

Sample Output 1
agfedcb

Explanation 1

Split the string into two strings with like characters: $abcdefg$ and $abcdefg$. 

Reverse $abcdefg$ = $gfeedcba$ 

Shuffle $gfeedcba$ can be $bcdefga$ 

Merge to $\boldsymbol{\alpha}$bcdefga$bcdefg$    

Sample Input 2
aeiouuoiea

Sample Output 2
aeiou

Explanation 2

Split the string into groups of like characters: $a e i o u$ 

Reverse $a e i o u$ = $u o iea$ 

These merge to $a e i o u$uoiea

Difficulty: HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import Counter, defaultdict
from bisect import bisect

def solve(s):
	word = Counter(s)
	for (k, v) in word.items():
		word[k] = v // 2
	revleft = word.copy()
	(skipped, avail) = (Counter(), Counter())
	locs = defaultdict(list)
	for (i, c) in enumerate(s):
		locs[c].append(i)
	ans = []
	live = len(s) - 1
	dead = len(s)
	while revleft:
		leftc = s[live]
		avail[leftc] += 1
		while avail[leftc] + skipped[leftc] > word[leftc]:
			cnew = min((c for c in avail.keys() if avail[c] > 0 and revleft[c] > 0))
			ans.append(cnew)
			avail[cnew] -= 1
			revleft[cnew] -= 1
			if revleft[cnew] == 0:
				del revleft[cnew]
			i = bisect(locs[cnew], dead - 1) - 1
			i = locs[cnew][i]
			assert s[i] == cnew
			for c in s[i + 1:dead]:
				avail[c] -= 1
				skipped[c] += 1
			dead = i
			assert live <= i
		live -= 1
	return ''.join(ans)
print(solve(input()))


from collections import defaultdict
S = input()
S = S[::-1]
count = defaultdict(int)
for c in S:
	count[c] += 1
need = {}
for c in count:
	need[c] = count[c] / 2
solution = []
i = 0
while len(solution) < len(S) / 2:
	min_char_at = -1
	while True:
		c = S[i]
		if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
			min_char_at = i
		count[c] -= 1
		if count[c] < need[c]:
			break
		i += 1
	for j in range(min_char_at + 1, i + 1):
		count[S[j]] += 1
	need[S[min_char_at]] -= 1
	solution.append(S[min_char_at])
	i = min_char_at + 1
print(''.join(solution))


s = input()
from collections import Counter
need = Counter(s)
for k in need:
	need[k] //= 2
ans = ''
r = s[::-1]
pos = 0
seen = Counter()
fill = Counter()
while need:
	filled = False
	for target in sorted(need):
		if filled:
			break
		tmp = seen.copy()
		now = pos
		while True:
			char = r[now]
			now += 1
			tmp[char] += 1
			if char == target:
				ans += target
				fill[target] += 1
				filled = True
				if fill[target] == need[target]:
					del need[target]
				pos = now
				seen = tmp.copy()
				break
			if char > target and need[char] and (tmp[char] - fill[char] > need[char]):
				break
print(ans)


from collections import Counter

def lmo(fullstr):
	fullstr_remaining_counts = Counter(fullstr)
	counts_to_delete = Counter(fullstr_remaining_counts)
	for char in counts_to_delete:
		counts_to_delete[char] //= 2
	counts_to_keep = Counter(counts_to_delete)
	out_str = list(reversed(fullstr))
	to_delete = set()
	for i in range(len(out_str)):
		if i in to_delete:
			continue
		if not counts_to_keep[out_str[i]]:
			to_delete.add(i)
			counts_to_delete[out_str[i]] -= 1
			continue
		counts_to_go = Counter(counts_to_delete)
		min_char = out_str[i]
		min_idx = i
		for j in range(i, len(out_str)):
			cur_char = out_str[j]
			if cur_char < min_char and counts_to_keep[cur_char]:
				min_char = cur_char
				min_idx = j
			if counts_to_go[cur_char]:
				counts_to_go[cur_char] -= 1
			else:
				break
		if min_idx > i:
			for j in range(i, min_idx):
				to_delete.add(j)
				counts_to_delete[out_str[j]] -= 1
		else:
			counts_to_keep[min_char] -= 1
	for index in sorted(to_delete, reverse=True):
		del out_str[index]
	return ''.join(out_str)
print(lmo(input().strip()))


from collections import defaultdict

def find(S):
	length = len(S)
	freq = defaultdict(int)
	needs = {}
	A = []
	R = S[::-1]
	for c in S:
		freq[c] += 1
	for c in freq:
		needs[c] = freq[c] / 2
	index = 0
	while len(A) < length / 2:
		minimum = -1
		while True:
			c = R[index]
			if needs[c] > 0 and (minimum < 0 or c < R[minimum]):
				minimum = index
			freq[c] -= 1
			if freq[c] < needs[c]:
				break
			index += 1
		for j in range(minimum + 1, index + 1):
			freq[R[j]] += 1
		needs[R[minimum]] -= 1
		A.append(R[minimum])
		index = minimum + 1
	return ''.join(A)

def main():
	print(find(input()))
main()


S = list(map(lambda x: ord(x) - 97, input()))
S = list(reversed(S))
T = [0 for _ in range(26)]
for x in S:
	T[x] += 1
R = list(map(lambda x: x // 2, T))
stack = []
for x in S:
	T[x] -= 1
	if not R[x]:
		continue
	while stack and stack[-1] > x and (T[stack[-1]] > R[stack[-1]]):
		R[stack[-1]] += 1
		stack.pop()
	if R[x]:
		stack.append(x)
		R[x] -= 1
stack = list(map(lambda x: chr(x + 97), stack))
print(''.join(stack))


from collections import Counter, deque
string = input()
string_counter = dict(Counter(string))
string_counter = Counter({key: value // 2 for (key, value) in string_counter.items()})
ordering_of_characters = deque(sorted(string_counter.elements()))
encountered_string_counter = Counter()
skipped_characters = []
key = []
for character in reversed(string):
	encountered_string_counter += Counter(character)
	if len(ordering_of_characters) == 0:
		break
	if character not in ordering_of_characters:
		continue
	if encountered_string_counter[character] - key.count(character) > string_counter[character]:
		this_skipped_characters = []
		if len(skipped_characters) > 0:
			ordering_of_skipped_characters = deque(sorted(skipped_characters))
			for skipped_character in skipped_characters:
				if skipped_character > character:
					continue
				if skipped_character == character:
					if skipped_character == ordering_of_skipped_characters[0]:
						this_skipped_characters.append(character)
					continue
				if skipped_character not in ordering_of_characters:
					continue
				if skipped_character == ordering_of_skipped_characters[0]:
					key.append(skipped_character)
					ordering_of_skipped_characters.popleft()
					ordering_of_characters.remove(skipped_character)
				else:
					ordering_of_skipped_characters.remove(skipped_character)
		key.append(character)
		ordering_of_characters.remove(character)
		skipped_characters = this_skipped_characters
		continue
	if character == ordering_of_characters[0]:
		key.append(character)
		ordering_of_characters.popleft()
		skipped_characters = []
	else:
		skipped_characters.append(character)
print(''.join(key))


from collections import defaultdict

def solve(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
print(solve(input()))
import doctest
doctest.testmod()


string = input()
dictString = {}
letters = 0
stringCopy = []
setlString = []
for i in range(len(string) - 1, -1, -1):
	letters += 0.5
	stringCopy.append(string[i])
	if string[i] not in dictString:
		dictString[string[i]] = 0.5
		setlString.append(string[i])
	else:
		dictString[string[i]] += 0.5
output = ''
setlString.sort()
stringCopy = ''.join(stringCopy)
while letters > 0:
	testChar = ''
	sortIndex = 0
	while testChar == '':
		testChar = setlString[sortIndex]
		endString = stringCopy[stringCopy.index(testChar):]
		if len(endString) < letters:
			testChar = ''
			sortIndex += 1
			continue
		okChar = True
		for key in setlString:
			if key == testChar:
				continue
			if dictString[key] > endString.count(key):
				okChar = False
				break
		if okChar:
			dictString[testChar] -= 1
			output += testChar
			letters -= 1
			if dictString[testChar] == 0:
				del dictString[testChar]
				setlString.remove(testChar)
				stringCopy = endString.replace(testChar, '')
			else:
				stringCopy = endString[1:]
		else:
			testChar = ''
			sortIndex += 1
output = list(output)
print(''.join(output))


import re
from collections import Counter

def move_foward(a, s, p, q, m, counterA, counterB, counterS):
	c = s[p]
	counterB[c] += 1
	if chr(a[q]) == c:
		counterA[c] -= 1
		for x in counterB:
			counterS[x] -= counterB[x]
			counterB[x] = 0
		q += 1
		m = p + 1
	elif counterS[c] - counterB[c] < counterA[c]:
		t = q + 1
		while a[q] >= a[t]:
			t += 1
		(a[q], a[t]) = (a[t], a[q])
		counterB.clear()
		return (m, q, m)
	return (p + 1, q, m)
s = ''.join(reversed(list(input())))
counterS = Counter(s)
a = ''.join(sorted([x * (counterS[x] // 2) for x in counterS]))
counterA = Counter(a)
counterB = Counter({})
a = [ord(x) for x in a]
PR = False
(p, q, m) = (0, 0, 0)
while q < len(a):
	(p, q, m) = move_foward(a, s, p, q, m, counterA, counterB, counterS)
print(''.join(map(chr, a)))


s = input()
n = len(s)
t = [0] * 26
pos = [[] for i in range(26)]
for i in range(n):
	t[ord(s[i]) - ord('a')] += 1
	pos[ord(s[i]) - ord('a')] += [i]
for i in range(26):
	t[i] //= 2
v = ''
m = [0] * 26
for i in range(26):
	m[i] = t[i] - 1
j = n - 1
while j >= 0:
	ma = -1
	for k in range(26):
		if m[k] >= 0:
			ma = max(ma, pos[k][m[k]])
	if j == ma:
		v += s[j]
		k = ord(s[j]) - ord('a')
		m[k] -= 1
		j -= 1
	elif ma >= 0:
		x = ma
		y = ord(s[ma]) - ord('a')
		for k in range(ma + 1, j + 1):
			h = ord(s[k]) - ord('a')
			if h <= y and m[h] >= 0:
				y = h
				x = k
		v += s[x]
		m[y] -= 1
		j = x - 1
	else:
		j = -1
print(v)


from collections import Counter

def smallest(S):
	(l, count, right, res, R, i) = (len(S), Counter(S), {}, '', S[::-1], 0)
	for x in count:
		right[x] = count[x] // 2
	while len(res) < l // 2:
		m = -1
		while True:
			t = R[i]
			if right[t] > 0 and (m < 0 or t < R[m]):
				m = i
			count[t] -= 1
			if count[t] < right[t]:
				break
			i += 1
		for j in range(m + 1, i + 1):
			count[R[j]] += 1
		right[R[m]] -= 1
		res += R[m]
		i = m + 1
	return res
print(smallest(input()))


ALL_LOWERCASE_LETTERS = 'abcdefghijklmnopqrstuvwxyz'

def calcLastBeforeIdx(line, letter, lineLastIdx):
	while lineLastIdx >= 0 and line[lineLastIdx] != letter:
		lineLastIdx -= 1
	return lineLastIdx
line = input()
letterXpos_to_count_dic = dict()
for letter in ALL_LOWERCASE_LETTERS:
	letterXpos_to_count_dic[letter, -1] = 0
for i in range(len(line)):
	for letter in ALL_LOWERCASE_LETTERS:
		if letter == line[i]:
			letterXpos_to_count_dic[letter, i] = letterXpos_to_count_dic[letter, i - 1] + 1
		else:
			letterXpos_to_count_dic[letter, i] = letterXpos_to_count_dic[letter, i - 1]
letter_to_count_dic_in_A = dict()
for letter in ALL_LOWERCASE_LETTERS:
	letter_to_count_dic_in_A[letter] = letterXpos_to_count_dic[letter, len(line) - 1] / 2
ret = ''
lineLastIdx = len(line) - 1
for i in range(len(line) // 2 - 1, -1, -1):
	for letter in ALL_LOWERCASE_LETTERS:
		if letter_to_count_dic_in_A[letter] <= 0:
			continue
		lastBeforeIdx = calcLastBeforeIdx(line, letter, lineLastIdx)
		canAppendLetter = 1
		for letter2 in ALL_LOWERCASE_LETTERS:
			if letterXpos_to_count_dic[letter2, lastBeforeIdx] < letter_to_count_dic_in_A[letter2]:
				canAppendLetter = 0
				break
		if canAppendLetter:
			ret = ret + letter
			letter_to_count_dic_in_A[letter] = letter_to_count_dic_in_A[letter] - 1
			lineLastIdx = lastBeforeIdx - 1
			break
print(ret)


import collections
s = [ord(c) - ord('a') for c in input()]

def freq(s, start):
	result = [0] * 26
	for c in s[start:]:
		result[c] += 1
	return result
rev = s[::-1]
d = collections.defaultdict(list)
for (i, x) in enumerate(rev):
	d[x].append(i)
cnt = [x // 2 for x in freq(s, 0)]
p = 0
res = []
fpos = 0
f = [x * 2 for x in cnt]
while len(res) < len(s) // 2:
	for (i, count) in enumerate(cnt):
		if count > 0:
			mini = next((x for x in d[i] if p <= x), None)
			if mini is not None:
				sign = 1 if mini < fpos else -1
				ds = rev[mini:fpos] if mini < fpos else rev[fpos:mini]
				for c in ds:
					f[c] += sign
				fpos = mini
				if all(map(lambda t: t[0] <= t[1], zip(cnt, f))):
					p = mini + 1
					cnt[i] -= 1
					res.append(i)
					break
print(''.join((chr(i + ord('a')) for i in res)))


def countChars(inp):
	C = [0] * 26
	ai = ord('a')
	for x in inp:
		i = ord(x) - ai
		C[i] = C[i] + 1
	return C

def getHalf(C):
	tmp = C[:]
	for i in range(26):
		tmp[i] = int(tmp[i] / 2)
	return tmp

def is1gte2(arr1, arr2, tmp_char):
	tmpi = ord(tmp_char) - ord('a')
	for i in range(26):
		if i == tmpi:
			if arr1[i] < arr2[i] - 1:
				return False
		elif arr1[i] < arr2[i]:
			return False
	return True

def modify_Csc(C_sc, list_chars):
	ai = ord('a')
	for x in list_chars:
		xi = ord(x) - ai
		C_sc[xi] = C_sc[xi] - 1

def minIutil(arr, l, r, C, C_sc):
	(m, i) = (r, r + 1)
	ai = ord('a')
	while i > l:
		i = i - 1
		if C[ord(arr[i]) - ai] > 0:
			m = i
			break
	while i > l:
		i = i - 1
		if ord(arr[i]) < ord(arr[m]) and C[ord(arr[i]) - ai] > 0:
			m = i
	modify_Csc(C_sc, arr[m:r + 1])
	return m

def minI(arr, l, r, C, C_sc):
	ai = ord('a')
	while l <= r:
		tmp = C_sc[:]
		j = minIutil(arr, l, r, C, tmp)
		l = j + 1
		if is1gte2(tmp, C, arr[j]):
			break
	return j

def print_util(i_list, arr):
	for i in i_list:
		print(arr[i], end='')
	print()

def rms(inp):
	Cinp = countChars(inp)
	C_sc = Cinp[:]
	C = getHalf(Cinp)
	size = len(inp)
	n = int(size / 2)
	ans = []
	ai = ord('a')
	(i, j) = (1, size)
	while i <= n:
		(l, r) = (n + 1 - i, j - 1)
		j = minI(inp, l - 1, r, C, C_sc[:])
		modify_Csc(C_sc, inp[j:r + 1])
		xi = ord(inp[j]) - ai
		C[xi] = C[xi] - 1
		if C[xi] < 0:
			print('incorrect choice of char')
			break
		ans.append(j)
		i = i + 1
	print_util(ans, inp)
usr_inp = input().strip()
rms(usr_inp)


offset = ord('a')
n_letters = ord('z') - offset + 1
s = list(map(lambda c: ord(c) - offset, input()[::-1]))
len_s = len(s)
cnt_s = [0] * n_letters
for c in s:
	cnt_s[c] += 1
len_a = len_s // 2
cnt_a = [0] * n_letters
for i in range(n_letters):
	cnt_a[i] = cnt_s[i] // 2
a = ''
i = j = 0
last_i = -1
while j < len_a:
	c = s[i]
	if cnt_s[c] <= cnt_a[c]:
		last_k = last_i
		for d in range(c):
			for k in range(last_k + 1, i):
				if not cnt_a[d]:
					break
				if s[k] != d:
					continue
				a += chr(offset + d)
				j += 1
				cnt_a[d] -= 1
				last_k = k
		for k in range(last_k + 1, i + 1):
			if s[k] != c:
				continue
			a += chr(offset + c)
			j += 1
			cnt_a[c] -= 1
			last_k = k
			break
		last_i = last_k
	i += 1
	cnt_s[c] -= 1
print(a)


s = input()
l = len(s)
s = s[::-1]
freq = [0] * 26
next_to_use = [0] * 26
positions = [[] for x in range(26)]
for i in range(l):
	bucket = ord(s[i]) - 97
	freq[bucket] += 1
	positions[bucket].append(i)
for x in range(26):
	freq[x] = int(freq[x] / 2)
	next_to_use[x] = 0
needs = [0] * l
freq_seen = [0] * 26
for i in range(l - 1, 0, -1):
	bucket = ord(s[i]) - 97
	needs[i] = freq[bucket] - freq_seen[bucket]
	freq_seen[bucket] = min(freq_seen[bucket] + 1, freq[bucket])
answer = ''
next_bottleneck = 0
last_pos = 0
written = [0] * 26
while len(answer) != int(l / 2):
	while not written[ord(s[next_bottleneck]) - 97] < needs[next_bottleneck]:
		next_bottleneck += 1
	next_char = 0
	while written[next_char] == freq[next_char] or positions[next_char][next_to_use[next_char]] > next_bottleneck:
		next_char += 1
	str_pos = positions[next_char][next_to_use[next_char]]
	while last_pos != str_pos:
		next_to_use[ord(s[last_pos]) - 97] += 1
		last_pos += 1
	run = True
	while run:
		answer += chr(next_char + 97)
		written[next_char] += 1
		next_to_use[next_char] += 1
		run = written[next_char] < needs[str_pos]
	last_pos = str_pos + 1
print(answer)


s = input()
count = {}
for c in s:
	count[c] = count.get(c, 0) + 1
Rcount = {c: count[c] // 2 for c in count}
Scount = {c: count[c] // 2 for c in count}
(o, i) = ('', len(s) - 1)
for _ in range(len(s) // 2):
	for c in sorted(Rcount):
		valid = True
		j = i
		while j >= 0 and s[j] != c:
			Scount[s[j]] -= 1
			if Scount[s[j]] < 0:
				valid = False
				break
			j -= 1
		if not valid:
			while j <= i:
				Scount[s[j]] += 1
				j += 1
			continue
		Rcount[c] -= 1
		o += c
		i = j - 1
		if Rcount[c] <= 0:
			del Rcount[c]
		break
print(o)


s = input()
g = [0] * 26
for c in s:
	g[ord(c) - 97] += 1
ans = []
f = [i // 2 for i in g]
m = len(s) // 2
idx = len(s) - 1
while len(ans) < m:
	k = -1
	while True:
		x = ord(s[idx]) - 97
		g[x] -= 1
		if f[x] > 0:
			if k < 0 or s[idx] < s[k]:
				k = idx
			if g[x] < f[x]:
				for j in range(idx, k):
					g[ord(s[j]) - 97] += 1
				break
		idx -= 1
	ans.append(s[k])
	f[ord(s[k]) - 97] -= 1
	idx = k - 1
print(''.join(ans))


import sys

def element(s):
	set = []
	for e in s:
		a = True
		for x in set:
			if e == x[0]:
				a = False
				x[1] += 1
				x[4] += 1
		if a:
			set.append([e, 1, 0, 0, 1])
	return set
s = input().strip()
v = s[::-1]
N = len(s) // 2
N_full = len(s)
se = element(v)
N_1 = len(se)
for u in se:
	u[1] = u[1] // 2
	u[4] = u[4] // 2
se_1 = sorted(se, key=lambda u: u[0])
new_str = []
len_shu = N
l = 0
l_1 = 0
len_shuffle = 0
count = 0
for i in range(N):
	for j in range(N_1):
		if se_1[j][1] == 0:
			continue
		for e in se_1:
			e[2] = 0
		l = l_1
		if v[l] == se_1[j][0]:
			se_1[j][1] = se_1[j][1] - 1
			new_str.append(se_1[j][0])
			l_1 = l + 1
			break
		else:
			test = True
			while v[l] != se_1[j][0]:
				for e in se_1:
					if e[0] == v[l]:
						e[2] += 1
						if e[2] + e[3] > e[4] or len_shuffle + l - l_1 > len_shu:
							test = False
							break
						break
				if test == False:
					break
				else:
					l += 1
			if test:
				for e in se_1:
					e[3] = e[3] + e[2]
				new_str.append(se_1[j][0])
				se_1[j][1] = se_1[j][1] - 1
				len_shuffle = len_shuffle + l - l_1
				l_1 = l + 1
				break
new_st = ''.join(new_str)
print(new_st)


import sys

def str_to_ints(s):
	return [ord(_) - ord('a') for _ in s]

def ints_to_str(s_ints):
	return ''.join((chr(_ + ord('a')) for _ in s_ints))

def freq_list(s_ints):
	f = [0] * 26
	for _ in s_ints:
		f[_] += 1
	return [_ // 2 for _ in f]

def find_lowest_possible_letter(s_ints):
	for _ in range(len(s_ints)):
		if s_ints[_]:
			return _
s = input().strip()
si = str_to_ints(s)
r_ltrs = freq_list(si)
s_ltrs = r_ltrs.copy()
a = []
letters_needed = len(s) // 2
best_so_far = len(si)
while letters_needed:
	ideal_letter = find_lowest_possible_letter(r_ltrs)
	best_so_far -= 1
	s_ltrs[si[best_so_far]] -= 1
	while not r_ltrs[si[best_so_far]]:
		best_so_far -= 1
		s_ltrs[si[best_so_far]] -= 1
	look_index = best_so_far - 1
	found = False
	while not found:
		if si[best_so_far] == ideal_letter or s_ltrs[si[best_so_far]] == -1:
			found = True
		elif si[look_index] < si[best_so_far] and r_ltrs[si[look_index]]:
			best_so_far = look_index
			s_ltrs[si[best_so_far]] -= 1
			look_index -= 1
		elif s_ltrs[si[look_index]]:
			s_ltrs[si[look_index]] -= 1
			look_index -= 1
		else:
			for _ in range(look_index + 1, best_so_far):
				s_ltrs[si[_]] += 1
			found = True
	a.append(si[best_so_far])
	s_ltrs[si[best_so_far]] += 1
	r_ltrs[si[best_so_far]] -= 1
	letters_needed -= 1
print(ints_to_str(a))


from collections import Counter
inpt = input()
pool = list(''.join((char * (count // 2) for (char, count) in Counter(inpt).items())))
(srtd, rvsd) = (list(sorted(pool)), list(reversed(inpt)))
(a, srtd_idx, rvsd_idx) = ('', 0, 0)
while srtd:
	while True:
		tmp_pool = list(pool)
		end_while = False
		for c in rvsd[rvsd_idx:]:
			if c == srtd[srtd_idx]:
				end_while = True
				break
			if c in tmp_pool:
				tmp_pool.remove(c)
			else:
				break
		if end_while:
			break
		while srtd[srtd_idx] == srtd[srtd_idx + 1]:
			srtd_idx += 1
		srtd_idx += 1
	a += srtd.pop(srtd_idx)
	rvsd_idx += len(pool) - len(tmp_pool) + 1
	pool = tmp_pool
	srtd_idx = 0
print(a)


def occurence(b, m):
	a = 0
	for i in range(len(m)):
		if m[i] == b:
			a += 1
	return a
m = input().strip()
m = m[::-1]
a = {}
for i in range(len(m)):
	if m[i] not in a:
		a[m[i]] = 1 / 2
	else:
		a[m[i]] += 1 / 2
i = 0
h = []
k = []
z = 0
while i < len(m):
	if i == 0:
		h = [m[0]]
		k = [0]
		a[m[0]] -= 1
		i = i + 1
	elif m[i] < m[i - 1] and occurence(m[i - 1], m[i:]) > int(a[m[i - 1]]) and (i > 0) and (int(a[m[i]]) != 0) and (occurence(m[i - 1], m[i:]) != 0):
		z = 1
		if i - 1 in k:
			k.pop(-1)
			h.pop(-1)
			a[m[i - 1]] += 1
		m = m[:i - 1] + m[i:]
		i -= 1
	elif occurence(m[i], m[i:]) >= int(a[m[i]]) and int(a[m[i]]) != 0:
		if i not in k:
			k.append(i)
			h.append(m[i])
			a[m[i]] -= 1
		i += 1
	else:
		m = m[:i] + m[i + 1:]
for i in h:
	print(i, end='')


import bisect
s = input()
a_chars = sorted(s)[::2]
a_shuf = a_chars.copy()
a_best = ''
visited = []
for c in s[::-1]:
	if a_chars and c == a_chars[0]:
		a_best += c
		a_chars.remove(c)
		visited = []
	elif c not in a_shuf:
		if visited:
			while visited and visited[0] < c:
				t = visited.pop(0)
				if t in a_chars:
					a_best += t
					a_chars.remove(t)
					a_shuf.append(t)
		a_best += c
		a_chars.remove(c)
		visited = [c] * visited.count(c)
	else:
		a_shuf.remove(c)
		if c in a_chars:
			bisect.insort(visited, c)
			visited = visited[:visited.index(c) + visited.count(c)]
print(a_best)


s = input()
d = {}
for x in s:
	if d.__contains__(x):
		d[x] += 1
	else:
		d[x] = 1
ans = ''
for x in d:
	d[x] = d[x] / 2
check = ''
check = {x: d[x] for x in d}
written = {x: 0 for x in d}
needs = {x: 0 for x in d}
need = []
letters = [x for x in d]
letters.sort()
s = [x for x in s]
s.reverse()
reqs = []
ans = ''
sub = ''
for i in range(len(s)):
	if d[s[i]] == 0:
		needs[s[i]] += 1
		reqs.append(i)
		need.append(needs[s[i]])
	else:
		d[s[i]] -= 1
		need.append(0)
i = 0
curr = 0
lastw = -1
while i < len(s):
	if written[s[i]] >= need[i]:
		i += 1
		continue
	lim = i
	for c in letters:
		if c > s[lim]:
			curr += 1
			i += 1
			break
		for j in range(lastw + 1, lim):
			char = s[j]
			if char == c and written[c] < check[c]:
				ans += c
				lastw = j
				written[c] += 1
	if written[s[lim]] < need[lim]:
		ans += s[lim]
		written[s[lim]] += 1
		lastw = lim
print(ans)


def recover(s):
	s = s[::-1]
	count = {}
	for c in s:
		if c in count:
			count[c] += 1
		else:
			count[c] = 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	a = []
	i = 0
	while len(a) < len(s) / 2:
		min_char = -1
		while True:
			c = s[i]
			if need[c] > 0 and (min_char < 0 or c < s[min_char]):
				min_char = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char + 1, i + 1):
			count[s[j]] += 1
		need[s[min_char]] -= 1
		a.append(s[min_char])
		i = min_char + 1
	return ''.join(a)
print(recover(input()))


import sys
from copy import copy
from collections import Counter
s = sys.stdin.readline().strip()[::-1]
creq = dict(Counter(s))
for c in creq.keys():
	creq[c] /= 2
result = ''
start_pos = 0
se = list(reversed(list(enumerate(s))))
while len(result) != len(s) / 2:
	cur_stat = copy(creq)
	last_pos = None
	for (i, c) in se:
		last_pos = i
		if c not in cur_stat.keys():
			continue
		cur_stat[c] -= 1
		if cur_stat[c] == 0:
			del cur_stat[c]
		if len(cur_stat) == 0:
			break
	for c in sorted(creq.keys()):
		min_pos = s.find(c, start_pos, last_pos + 1)
		if min_pos == -1:
			continue
		start_pos = min_pos + 1
		result += c
		creq[c] -= 1
		if creq[c] == 0:
			del creq[c]
		break
print(result)


from collections import Counter
from itertools import product, permutations
import sys
sys.setrecursionlimit(9000)
input_str = input().strip()

def possible(string1, string2, counter):
	counter = counter.copy()
	while string1 and string2:
		pos = string2.find(string1[0])
		if pos != -1:
			counter.subtract(string1[0])
			string1 = string1[1:]
			string2 = string2[pos + 1:]
		else:
			string2 = string2[1:]
	counter_rest = Counter(string2)
	return (all([True if counter_rest[key] >= counter[key] else False for key in counter]), string2)

def add_letter(text, counter, rest):
	first = True
	for letter in [s for s in sorted(counter) if counter[s] != 0]:
		if not first:
			counter.update(text.pop())
		else:
			first = False
		text.append(letter)
		counter.subtract(letter)
		if not bool([c for c in counter if counter[c] != 0]):
			return ''.join(text)
		(pos, rest_new) = possible(letter, rest, counter)
		if pos:
			t = add_letter(text, counter, rest_new)
			if t:
				return t
	if text:
		counter.update(text.pop())
	return text

def eggegg(input_str):
	count = Counter(input_str)
	for c in count:
		count[c] = int(count[c] / 2)
	solution = ''.join(add_letter([], count, input_str[::-1]))
	print(solution)
	return solution
eggegg(input_str)


from collections import Counter
S = input()[::-1]
A_built = list()
A_left = sorted(S)
A_left = A_left[0::2]
A_left_cnt = Counter(A_left)
S_left_cnt = Counter(S)
S_cursor = 0
while sum(A_left_cnt.values()) > 0:
	for let in sorted(A_left_cnt.keys()):
		first_occurence = S.find(let, S_cursor)
		thrown = Counter(S[S_cursor:first_occurence])
		if all((S_left_cnt[x] - thrown[x] - A_left_cnt[x] >= 0 for x in A_left_cnt.keys())):
			S_left_cnt -= thrown
			temp = Counter([let])
			S_left_cnt -= temp
			A_left_cnt -= temp
			S_cursor = first_occurence + 1
			A_built.append(let)
			break
print(''.join(A_built))


from collections import defaultdict
import doctest

def solve(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
print(solve(input()))
doctest.testmod()


import collections
import copy

def solve(input_str):
	keeps = collections.defaultdict(int)
	for ch in input_str:
		keeps[ch] += 1
	for ch in keeps:
		keeps[ch] //= 2
	skips = copy.deepcopy(keeps)
	result_list = []
	for ch in reversed(input_str):
		if not keeps[ch]:
			skips[ch] -= 1
			continue
		while result_list and skips[result_list[-1]] and (ch < result_list[-1]):
			keeps[result_list[-1]] += 1
			skips[result_list[-1]] -= 1
			result_list.pop()
		keeps[ch] -= 1
		result_list.append(ch)
	return ''.join(result_list)
print(solve(input()))


from collections import defaultdict

def solve(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
print(solve(input()))


def canDoBetter(char, mot, indice, lettres):
	liste = list(lettres)
	dico2 = dict(dico)
	for i in range(len(mot) - indice, len(mot)):
		if len(liste) == 0:
			break
		if mot[-1 - i] == liste[0]:
			return True
		elif mot[-1 - i] in liste and mot[-1 - i] < char:
			return True
		elif dico2[mot[-1 - i]] == 0 and mot[-1 - i] in liste:
			if mot[-1 - i] > char:
				return False
			else:
				liste.remove(mot[-1 - i])
		else:
			dico2[mot[-1 - i]] = max(dico2[mot[-1 - i]] - 1, 0)
	return False
mot = input()
dico = {}
lettres = ''
for c in mot:
	if c in dico.keys():
		dico[c] += 0.5
		if int(dico[c]) == dico[c]:
			lettres += c
	else:
		dico[c] = 0.5
lettres = sorted(lettres)
res = ''
for i in range(len(mot)):
	if len(lettres) == 0:
		break
	if mot[-1 - i] == lettres[0]:
		lettres.pop(0)
		dico[mot[-1 - i]] = max(dico[mot[-1 - i]] - 1, 0)
		res += mot[-1 - i]
	elif mot[-1 - i] in lettres:
		if dico[mot[-1 - i]] != 0 and canDoBetter(mot[-1 - i], mot, len(mot) - i - 1, lettres):
			dico[mot[-1 - i]] = max(dico[mot[-1 - i]] - 1, 0)
		else:
			res += mot[-1 - i]
			lettres.remove(mot[-1 - i])
print(res)


S = input().strip()
slen = len(S)
T = ''
for ch in S:
	T = ch + T
(orda, ordz) = (ord('a'), ord('z'))
freqs = [T.count(chr(i + orda)) // 2 for i in range(0, 26)]
positions = [[] for i in range(0, 26)]
for i in range(0, slen):
	ch = T[i]
	positions[ord(ch) - orda].append(i)
written = [0 for i in range(0, 26)]
next2use = [0 for i in range(0, 26)]
needs = [0 for i in range(0, slen)]
for i in range(0, 26):
	if freqs[i] == 0:
		continue
	need = freqs[i]
	j = slen - 1
	while True:
		if T[j] == chr(i + orda):
			needs[j] = need
			need -= 1
			if need == 0:
				break
		j -= 1
A = ''
(nb, lp) = (0, 0)
while len(A) != len(T) // 2:
	while written[ord(T[nb]) - orda] >= needs[nb]:
		nb += 1
	nch = 0
	while written[nch] == freqs[nch] or positions[nch][next2use[nch]] > nb:
		nch += 1
	sp = positions[nch][next2use[nch]]
	while lp != sp:
		next2use[ord(T[lp]) - orda] += 1
		lp += 1
	A += chr(nch + orda)
	written[nch] += 1
	next2use[nch] += 1
	while written[nch] < needs[sp]:
		A += chr(nch + orda)
		written[nch] += 1
		next2use[nch] += 1
	lp = sp + 1
print(A)


from collections import Counter

def solve(S):
	S = S[::-1]
	C = Counter(S)
	N = {k: C[k] / 2 for k in C}
	(i, sol) = (0, [])
	while len(sol) < len(S) // 2:
		j = -1
		while True:
			if N[S[i]] and (j < 0 or S[i] < S[j]):
				j = i
			C[S[i]] -= 1
			if C[S[i]] < N[S[i]]:
				break
			i += 1
		for k in range(j + 1, i + 1):
			C[S[k]] += 1
		N[S[j]] -= 1
		sol.append(S[j])
		i = j + 1
	return ''.join(sol)
print(solve(input().strip()))


from collections import Counter

def find_char(ref_ctn, c, slist, startidx, endflag):
	if ref_ctn[c] == 0:
		return startidx
	idx = slist[startidx:].index(c) + startidx
	if endflag:
		ref_ctn[c] -= 1
		return idx + 1
	else:
		temp_ctn = Counter(slist[idx + 1:])
		if all((temp_ctn[j] >= ref_ctn[j] for j in list(ref_ctn) if ord(j) > ord(c))):
			ref_ctn[c] -= 1
			return idx + 1
		else:
			return startidx
s = input().strip()
c = Counter(s)
ctn = c
for x in list(ctn):
	ctn[x] = int(ctn[x] / 2)
slist = list(s)[::-1]
ctn_list = list(ctn.elements())
list_distinct = sorted(list(ctn))
ctn_list_sort = sorted(ctn_list)
n = len(ctn_list)
startidx = 0
alph_idx_main = 0
r = []
while len(r) < n:
	endflag = False
	if ctn[list_distinct[alph_idx_main]] > 0:
		alph_idx = alph_idx_main
		while find_char(ctn, list_distinct[alph_idx], slist, startidx, endflag) == startidx:
			alph_idx += 1
			if alph_idx == len(list_distinct) - 1:
				endflag = True
		startidx = slist[startidx:].index(list_distinct[alph_idx]) + startidx + 1
		r.append(startidx - 1)
	else:
		alph_idx_main += 1
stemp = ''.join([slist[x] for x in r])
print(stemp)


from random import randint, shuffle
DELTA = 97

def best_first_symbol(symbol_arr):
	for i in range(len(symbol_arr)):
		if symbol_arr[i] > 0:
			return chr(i + DELTA)
	return 'π'

def idx(char):
	return ord(char) - DELTA

def find_A(S, symbol_arr, skip_arr):
	if not S:
		return ''
	best_candidate = 'π'
	best_cand_index = -1
	i = 0
	result = []
	while True:
		if sum(symbol_arr) == 0:
			break
		best_symbol = best_first_symbol(symbol_arr)
		if symbol_arr[idx(S[i])] == 0:
			i += 1
		elif S[i] == best_symbol:
			symbol_arr[idx(S[i])] -= 1
			result.append(S[i])
			best_candidate = 'π'
			i += 1
		elif skip_arr[idx(S[i])] > 0:
			if S[i] < best_candidate:
				best_candidate = S[i]
				best_cand_index = i
				skip_arr_copy = skip_arr.copy()
			skip_arr[idx(S[i])] -= 1
			i += 1
		elif best_candidate != 'π' and best_candidate <= S[i]:
			result.append(best_candidate)
			symbol_arr[idx(best_candidate)] -= 1
			i = best_cand_index + 1
			skip_arr = skip_arr_copy.copy()
			best_candidate = 'π'
		else:
			symbol_arr[idx(S[i])] -= 1
			result.append(S[i])
			best_candidate = 'π'
			i += 1
	return ''.join(result)
symbol_arr = [0 for i in range(26)]
skip_arr = [0 for i in range(26)]
S = list(reversed(input().strip(' \n')))
for char in S:
	symbol_arr[ord(char) - DELTA] += 1
for i in range(len(symbol_arr)):
	val = symbol_arr[i] // 2
	symbol_arr[i] = val
	skip_arr[i] = val
print(find_A(S, symbol_arr, skip_arr))


from collections import Counter
original = s = input()
counter = Counter(s)
for k in counter:
	counter[k] //= 2
word = ''
while len(word) < len(original) // 2:
	for c in sorted(counter.keys()):
		i = s.rfind(c)
		left = Counter(s[:i + 1])
		if all((k in left and left[k] >= counter[k] for k in counter)):
			word += c
			s = s[:i]
			counter[c] -= 1
			if counter[c] == 0:
				del counter[c]
			break
print(word)


def get_freq(s):
	freq = [0] * 26
	for x in s:
		freq[ord(x) - 97] += 1
	return freq

def min_RSM_Lexical(s):
	s = s[::-1]
	len_s = len(s)
	freq = get_freq(s)
	freqActual = list(freq)
	letters = [[chr(i + 97), freq[i]] for i in range(26)]
	answer = []
	letterIndex = 0
	while sum(freq) != 0:
		while letters[letterIndex][1] < 1:
			letterIndex += 1
			if letterIndex == 26:
				return ''.join(answer)
		letter = letters[letterIndex][0]
		i = s.index(letter)
		freqLeft = get_freq(s[:i])
		freqRight = [freqActual[k] - freqLeft[k] for k in range(26)]
		foundIt = True
		for j in range(26):
			if freqRight[j] < freq[j] / 2:
				foundIt = False
		if foundIt:
			answer.append(letter)
			s = s[i + 1:]
			freqActual = list(freqRight)
			freqActual[ord(letter) - 97] -= 1
			letters[ord(letter) - 97][1] -= 2
			freq = [letters[i][1] for i in range(26)]
			letterIndex = 0
		else:
			letterIndex += 1
	return ''.join(answer)
print(min_RSM_Lexical(input()))


from collections import Counter
from collections import OrderedDict
from collections import deque

def get_index(s, idx, ordered_half, counts, options):
	c = s[idx]
	if c not in ordered_half:
		return -1
	if c == next(iter(ordered_half.keys())):
		return idx
	if ordered_half[c] == counts[c]:
		if options:
			first = sorted(options.items(), key=lambda t: t[0])[0]
			if c < first[0]:
				return idx
			else:
				return first[1]
		else:
			return idx
	if c not in options:
		options[c] = idx
	return -1

def solve(s):
	counts = Counter(s)
	half_d = dict()
	for (k, v) in counts.items():
		half_d[k] = v // 2
	ordered_half = OrderedDict(sorted(half_d.items(), key=lambda t: t[0]))
	selected = deque()
	options = dict()
	cur = len(s) - 1
	while cur >= 0:
		idx = get_index(s, cur, ordered_half, counts, options)
		if idx != -1:
			selected.append(s[idx])
			if ordered_half[s[idx]] == 1:
				ordered_half.pop(s[idx])
				if len(ordered_half) == 0:
					break
			else:
				ordered_half[s[idx]] -= 1
			while cur < idx:
				cur += 1
				counts[s[cur]] += 1
			if options:
				options.clear()
		counts[s[cur]] -= 1
		cur -= 1
	return ''.join(selected)
print(solve(input().strip()))


def solve(s):
	from collections import Counter, OrderedDict
	required_freq = OrderedDict()
	symbols_count = Counter(s)
	for c in sorted(symbols_count):
		required_freq[c] = symbols_count[c] // 2
	a = []
	freq_keys = list(required_freq.keys())
	min_key = freq_keys[0]
	required_to_take = []
	for i in range(len(s) - 1, -1, -1):
		c = s[i]
		req_val = required_freq[c]
		if req_val == 0:
			continue
		save = False
		if c in required_to_take:
			save = True
		elif min_key == c:
			save = True
		else:
			j = i - 1
			sc_copy = symbols_count.copy()
			while j >= 0 and (s[j] >= c or required_freq[s[j]] == 0):
				if s[j] in required_to_take or sc_copy[s[j]] == required_freq[s[j]]:
					if s[j] > c:
						save = True
					break
				sc_copy[s[j]] -= 1
				j -= 1
		if save:
			a.append(c)
			req_val -= 1
			if req_val == 0:
				del freq_keys[freq_keys.index(c)]
				if min_key == c and len(freq_keys) > 0:
					min_key = freq_keys[0]
		required_freq[c] = req_val
		symbols_count[c] -= 1
		if symbols_count[c] == req_val and c not in required_to_take:
			required_to_take.append(c)
	return ''.join(a)
print(solve(input()))


import sys

def estractMeta(word):
	list = [0] * 26
	a = ord('a')
	for char in word:
		list[ord(char) - a] += 1
	return list
word = input().strip()[::-1]
a = ord('a')
word_len = len(word)
meta = estractMeta(word)
meta_word = [0] * word_len
meta_bk = meta[:]
meta = [i / 2 for i in meta]
count = word_len / 2
for i in range(word_len):
	meta_word[i] = meta_bk[ord(word[i]) - a]
	meta_bk[ord(word[i]) - a] -= 1
char_index = []
min_char_index = 0
start_index = 0
while count > 0:
	min_char_index = -1
	for i in range(start_index, word_len):
		if meta[ord(word[i]) - a] <= 0:
			continue
		if min_char_index == -1:
			min_char_index = i
		if word[i] < word[min_char_index]:
			min_char_index = i
		if meta_word[i] == meta[ord(word[i]) - a]:
			break
	char_index.append(min_char_index)
	meta[ord(word[min_char_index]) - a] -= 1
	start_index = min_char_index + 1
	count -= 1
result = []
for i in char_index:
	result.append(word[i])
sys.stdout.write(str.join('', result))


from collections import Counter

def nextIndex(s, i, c, m, j=100000, n=1000):
	if ord(s[i]) < n and s[i] in c:
		n = ord(s[i])
		j = i
	if len(c - Counter(s[0:i])) or m == n:
		return j
	else:
		return nextIndex(s, i - 1, c, m, j, n)
s = input().strip()
chars = sorted(s)[::2]
m = ord(chars[0])
c = Counter(chars)
i = len(s)
out = ''
while len(c):
	i = nextIndex(s, i - 1, c, m)
	c = c - Counter(s[i])
	out += s[i]
print(out)


from collections import defaultdict

def solve(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
print(solve(input()))
import doctest
doctest.testmod()


merged = [c for c in input().strip()]
letters = [0 for i in range(26)]
for c in merged:
	letters[ord(c) - ord('a')] += 0.5
nxt = 0
while letters[nxt] == 0:
	nxt += 1
highest = len(merged) - 1
res = ''
sb = []
for i in reversed(range(len(merged))):
	if merged[:i].count(merged[i]) < letters[ord(merged[i]) - ord('a')]:
		if len(sb) > 0 and letters[ord(res[-1]) - ord('a')] > 0 and (ord(res[-1]) < ord(merged[i])):
			for c in sb:
				if c == res[-1]:
					res += c
					letters[ord(res[-1]) - ord('a')] -= 1
					if letters[ord(res[-1]) - ord('a')] == 0:
						break
		sb = merged[i + 1:highest][::-1]
		changed = True
		while len(sb) > 0 and changed:
			changed = False
			for k in range(nxt, ord(merged[i]) - ord('a')):
				while letters[k] > 0:
					if chr(k + ord('a')) in sb:
						res += chr(k + ord('a'))
						letters[k] -= 1
						sb = sb[sb.index(chr(k + ord('a'))) + 1:]
						changed = True
					else:
						break
		highest = i
		res += merged[i]
		letters[ord(merged[i]) - ord('a')] -= 1
	elif merged[i] == chr(ord('a') + nxt):
		highest = i
		res += merged[i]
		letters[nxt] -= 1
		while nxt < len(letters) and letters[nxt] == 0:
			nxt += 1
print(res)


from collections import Counter
import sys

def d(*args):
	pass
s = input()
usable = Counter(s)
for k in usable:
	usable[k] >>= 1
ignorable = usable.copy()
a = ''
f = reversed(s)
available = []
d('Searching through', f)
for (i, p) in enumerate(f):
	d('====== Step', i, ': our built string so far is %r' % a)
	d('Usable:   ', usable)
	d('Ignorable:', ignorable)
	if not usable:
		d('Nothing left to pick')
		break
	d('Is', p, 'the smallest (', sorted(usable)[0], ')?')
	if sorted(usable)[0] == p:
		usable[p] -= 1
		if usable[p] == 0:
			del usable[p]
		available = []
		a += p
		continue
	d('Are we forced to take', p, 'anyway? Can ignore', ignorable[p], 'more times.')
	while available and (not ignorable[p]):
		d('Are there any lexicographically smaller characters since the last one we took?', available)
		l = sorted(available)
		candidate = l[0][0]
		d('Candidate is', candidate, 'against', p)
		if candidate <= p:
			if usable[candidate]:
				d("It's better than what we'd get otherwise.")
				ignorable[candidate] += 1
				usable[candidate] -= 1
				if usable[candidate] == 0:
					del usable[candidate]
				a += candidate
		d('Removing everything from', available, 'that happened before or at index', l[0][1])
		available = [(k, v) for (k, v) in available if v > l[0][1]]
		d('Result:', available)
	if not ignorable[p]:
		usable[p] -= 1
		if usable[p] == 0:
			del usable[p]
		available = []
		a += p
		continue
	d('Just ignoring', p, 'for now.')
	ignorable[p] -= 1
	if ignorable[p] == 0:
		del ignorable[p]
	if usable[p]:
		available.append((p, i))
print(a)


from collections import defaultdict

def solve(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
print(solve(input()))


from collections import defaultdict
import math

def check(S, keep, c, indexCounter, index):
	tmpKeep = defaultdict(int)
	tmpKeep = {c: keep[c] for c in keep}
	for c in S[index:]:
		if c == i:
			break
		index += 1
	for (c, v) in indexCounter[index].items():
		tmpKeep[c] -= v
	for c in tmpKeep:
		if tmpKeep[c] > 0:
			return False
	return True
S = input()[::-1]
Cs = sorted(set(S))
counter = defaultdict(int)
indexCounter = defaultdict(lambda : defaultdict(int))
for (i, c) in reversed(list(enumerate(S))):
	indexCounter[i] = indexCounter[i + 1].copy()
	indexCounter[i][c] += 1
	counter[c] += 1
keep = defaultdict(int)
for c in counter:
	keep[c] = math.ceil(counter[c] / 2)
A = ''
index = 0
aLen = math.ceil(len(S) / 2)
for i in range(aLen):
	for i in Cs:
		if keep[i] > 0 and check(S, keep, i, indexCounter, index):
			A += i
			keep[i] -= 1
			for c in S[index:]:
				if c == i:
					index += 1
					break
				index += 1
			break
print(A)


def get_freq(s):
	freq = [0] * 26
	for char in s:
		freq[ord(char) - 97] += 1
	return freq

def find_window(s, need, l):
	c = 0
	for i in range(len(s) - 1, -1, -1):
		if need[ord(s[i]) - 97] > 0:
			need[ord(s[i]) - 97] -= 1
			c += 1
		if c == l:
			return i
	return -1

def find_smallest(s, start, end, letters):
	i = start
	while letters[ord(s[i]) - 97] <= 0:
		i += 1
	min_letter = s[i]
	min_ind = i
	for i in range(start, end + 1):
		if s[i] < min_letter and letters[ord(s[i]) - 97] > 0:
			min_letter = s[i]
			min_ind = i
	return (min_letter, min_ind)
s = input()
n = len(s)
l = int(len(s) / 2)
s = list(s[::-1])
need = get_freq(s)
for i in range(26):
	need[i] = int(need[i] / 2)
letters = need[:]
win_start = find_window(s, need, l)
start = 0
end = win_start
count = 0
output = []
while count < l:
	(min_letter, min_ind) = find_smallest(s, start, end, letters)
	letters[ord(s[min_ind]) - 97] -= 1
	count += 1
	output.append(min_letter)
	need = letters[:]
	win_start = find_window(s, need, l - count)
	start = min_ind + 1
	end = win_start
print(''.join(output))


from collections import defaultdict

def solution(S):
	S = S[::-1]
	count = defaultdict(int)
	for c in S:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(S) / 2:
		min_char_at = -1
		while True:
			c = S[i]
			if need[c] > 0 and (min_char_at < 0 or c < S[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[S[j]] += 1
		need[S[min_char_at]] -= 1
		solution.append(S[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
s = input()
print(solution(s))


import heapq

def find_subsequence(char_list, counts, subcounts):
	all_keys = set(counts)
	visited = {key: 0 for key in counts}
	added = {key: 0 for key in counts}
	substring = []
	min_idx = -1
	i = 0
	while i < len(char_list):
		c = char_list[i]
		if c in all_keys:
			visited[c] += 1
			if c == min(all_keys):
				added[c] += 1
				substring.append(c)
				min_idx = -1
			elif counts[c] - visited[c] < subcounts[c] - added[c]:
				if min_idx != -1 and char_list[min_idx] <= c:
					for j in range(min_idx + 1, i + 1):
						jchar = char_list[j]
						visited[jchar] -= 1
					c = char_list[min_idx]
					i = min_idx
					min_idx = -1
				added[c] += 1
				substring.append(c)
				min_idx = -1
			elif (c < char_list[min_idx] or min_idx == -1) and added[c] < visited[c]:
				min_idx = i
			if added[c] == subcounts[c]:
				all_keys -= {c}
		else:
			pass
		if len(all_keys) <= 0:
			break
		i += 1
	return substring
char_list = [c for c in input().strip()]
char_list.reverse()
counts = {}
for c in char_list:
	counts[c] = counts[c] + 1 if c in counts else 1
subcounts = {key: counts[key] // 2 for key in counts}
substring = find_subsequence(char_list, counts, subcounts)
print(''.join(substring).strip())


s = input().strip()
arr = [ord(c) - ord('a') for c in reversed(s)]
ori = [0] * 26
for i in arr:
	ori[i] += 1
ori = [c // 2 for c in ori]
min = [27, 0]
min_chosen = [0] * 26
min_left = [0] * 26
num_chosen = 0
max_chosen = len(arr) // 2
arr_chosen = list()
chosen = [0] * 26
left = [0] * 26
curr = 0
while curr < len(arr):
	c_curr = arr[curr]
	if chosen[c_curr] + 1 <= ori[c_curr]:
		if c_curr < min[0]:
			min = [c_curr, curr]
			min_chosen = chosen.copy()
			min_chosen[c_curr] += 1
			min_left = left.copy()
	if left[c_curr] + 1 <= ori[c_curr]:
		left[c_curr] += 1
		curr += 1
	else:
		arr_chosen.append(min[0])
		if len(arr_chosen) == max_chosen:
			print(''.join([chr(x + ord('a')) for x in arr_chosen]))
			exit(0)
		curr = min[1] + 1
		min = [27, 0]
		chosen = min_chosen
		left = min_left


def main():
	Solver(input().strip()).solve()

class Solver:

	def __init__(self, inputValue):
		self.inputValue = list(inputValue)

	def solve(self):
		sFrequency = Frequency()
		sFrequency.load(self.inputValue)
		aFrequency = sFrequency.half()
		strlen = len(self.inputValue)
		result = [None for _ in range(strlen // 2)]
		resultIndex = 0

		def genFunc(string):
			nonlocal aFrequency
			index = len(string) - 1
			while index >= 0:
				s = string[index]
				if aFrequency.isNeeded(s):
					newi = (yield (index, s))
					if newi is not None:
						yield
						index = newi
					else:
						index -= 1
				else:
					index -= 1
		generator = genFunc(self.inputValue)

		def consumeForced():
			nonlocal resultIndex, result, generator
			for x in generator:
				if sFrequency.isForced(x[1]):
					result[resultIndex] = x[1]
					resultIndex += 1
					sFrequency.subtract(x[1])
					aFrequency.subtract(x[1])
				else:
					generator.send(x[0])
					break

		def consumeUnforced():
			nonlocal resultIndex, result, generator
			minIndex = -1
			minValue = None
			snapshot = None
			isBroken = False
			for x in generator:
				if minValue is None or ord(x[1]) < ord(minValue):
					minIndex = x[0]
					minValue = x[1]
					snapshot = sFrequency.saveSnapshot()
				if sFrequency.isForced(x[1]):
					isBroken = True
					break
				sFrequency.subtract(x[1])
			if minValue is not None:
				result[resultIndex] = minValue
				resultIndex += 1
				sFrequency.loadSnapshot(snapshot)
				sFrequency.subtract(minValue)
				aFrequency.subtract(minValue)
				if isBroken:
					generator.send(minIndex - 1)
			elif isBroken:
				generator.send(x[0])
		for x in generator:
			generator.send(x[0])
			consumeForced()
			consumeUnforced()
			nex = next(generator, None)
			if nex is not None and nex != x:
				generator.send(nex[0])
		print(''.join(result))

class Frequency:
	a = ord('a')

	def __init__(self):
		self.frequency = [0 for i in range(26)]

	def load(self, string):
		for c in string:
			self.frequency[ord(c) - Frequency.a] += 1

	def isNeeded(self, c):
		return self.frequency[ord(c) - Frequency.a] > 0

	def subtract(self, c):
		self.frequency[ord(c) - Frequency.a] -= 1

	def isForced(self, c):
		cindex = ord(c) - Frequency.a
		return self.frequency[cindex] == self.half.frequency[cindex]

	def half(self):
		result = Frequency()
		for (index, count) in enumerate(self.frequency):
			result.frequency[index] = count // 2
		self.half = result
		return result

	def saveSnapshot(self):
		return list(self.frequency)

	def loadSnapshot(self, snapshot):
		self.frequency = snapshot
main()


from collections import Counter
data = input()
maxPassCounts = Counter(data)
passCounts = Counter()
sortedKey = sorted(maxPassCounts.keys())
skipped = {}
aCounts = Counter()
for i in maxPassCounts:
	maxPassCounts[i] //= 2
Astr = ''
minChar = sortedKey[0]
i = len(data) - 1

def SelectChar(k, i, skipped):
	if len(skipped) > 0 and min(skipped) <= k:
		k = min(skipped)
		reversePos = skipped[k]
		for tmp in range(i + 1, reversePos + 1):
			passCounts[data[tmp]] -= 1
		i = reversePos
	skipped.clear()
	aCounts[k] += 1
	return i
while i >= 0:
	k = data[i]
	if minChar == k:
		i = SelectChar(k, i, skipped)
		Astr += data[i]
		if k == minChar:
			if aCounts[k] == maxPassCounts[k]:
				for tmp in sortedKey:
					if aCounts[tmp] < maxPassCounts[tmp]:
						minChar = tmp
						break
	elif maxPassCounts[k] > passCounts[k]:
		passCounts[k] += 1
		if not skipped.__contains__(k) and aCounts[k] < maxPassCounts[k]:
			skipped[k] = i
	else:
		i = SelectChar(k, i, skipped)
		Astr += data[i]
		if k == minChar:
			if aCounts[k] == maxPassCounts[k]:
				for tmp in sortedKey:
					if aCounts[tmp] < maxPassCounts[tmp]:
						minChar = tmp
						break
	if len(Astr) == len(data) / 2:
		break
	i -= 1
print(Astr)


import string
alphabet = string.ascii_lowercase

def occurrences(s):
	d = {l: 0 for l in alphabet}
	for l in s:
		d[l] += 1
	return d

def compatible(reste, occ):
	return all((reste[l] >= occ[l] for l in alphabet))
s = input()
needed = occurrences(s)
for l in alphabet:
	needed[l] //= 2
skippable = needed.copy()
res = ''
for i in reversed(range(len(s))):
	add = False
	if not needed[s[i]]:
		continue
	smallest = min(filter(lambda l: needed[l], needed))
	if not skippable[s[i]] or s[i] == smallest:
		add = True
	elif i > 0:
		skippable_local = skippable.copy()
		for j in reversed(range(i)):
			if not needed[s[j]]:
				continue
			elif s[j] < s[i]:
				break
			elif skippable_local[s[j]] == 0:
				add = True
				break
			skippable_local[s[j]] -= 1
	if add:
		res += s[i]
		needed[s[i]] -= 1
	else:
		skippable[s[i]] -= 1
print(res)


def smallest_seed(string):
	cursor = Cursor(string)
	solution = create_solution_template(cursor.hist)
	position = cursor.save_position()
	next_char = solution.minimum_char()
	while solution.remaining_hist.size > 0:
		if cursor.hist.contains(solution.remaining_hist):
			if cursor.current_char() == next_char:
				solution.add(next_char)
				cursor.next_position()
				position = cursor.save_position()
				next_char = solution.minimum_char()
			else:
				cursor.next_position()
		else:
			next_char = solution.next_char()
			cursor.restore_position(position)
	return solution.string

def create_solution_template(hist):
	seed_hist = list(map(lambda n: n // 2, hist.hist))
	return Solution(Histogram(hist=seed_hist))

class Cursor:

	def __init__(self, string):
		self.hist = Histogram(string)
		self.string = string
		self.position = len(string) - 1

	def save_position(self):
		return self.position

	def restore_position(self, position):
		while self.position < position:
			self.prev_position()

	def next_position(self):
		self.hist.remove(self.string[self.position])
		self.position -= 1

	def prev_position(self):
		self.position += 1
		self.hist.add(self.string[self.position])

	def current_char(self):
		return self.string[self.position]

class Solution:

	def __init__(self, hist):
		self.string = ''
		self.char_pos = -1
		self.remaining_hist = hist

	def minimum_char(self):
		self.char_pos = -1
		for i in range(0, 26):
			if self.remaining_hist.hist[i] > 0:
				self.char_pos = i
				break
		return num_to_alpha(self.char_pos)

	def next_char(self):
		for i in range(self.char_pos + 1, 26):
			if self.remaining_hist.hist[i] > 0:
				self.char_pos = i
				break
		return num_to_alpha(self.char_pos)

	def add(self, c):
		self.string += c
		self.remaining_hist.remove(c)

class Histogram:

	def __init__(self, string='', hist=[0] * 26):
		self.hist = hist
		for c in iter(string):
			self.hist[alpha_to_num(c)] += 1
		self.size = sum(self.hist)

	def add(self, c):
		self.hist[alpha_to_num(c)] += 1
		self.size += 1

	def remove(self, c):
		self.hist[alpha_to_num(c)] -= 1
		self.size -= 1

	def size(self):
		return self.size

	def contains(self, other):
		return all([self.hist[i] >= other.hist[i] for i in range(0, 26)])

def alpha_to_num(c):
	return ord(c) - ord('a')

def num_to_alpha(n):
	return chr(n + ord('a'))
print(smallest_seed(input().strip()))


S = input()
length = len(S)
freq_need_a = {}
rev_S = S[::-1]
freq_s = {}
positions = {}
next_to_use = {}
for i in range(ord('a'), ord('z') + 1):
	freq_need_a[chr(i)] = 0
	freq_s[chr(i)] = 0
	next_to_use[chr(i)] = 0
	positions[chr(i)] = []
i = 0
while i < length:
	freq_s[rev_S[i]] += 1
	positions[rev_S[i]].append(i)
	i += 1
for i in freq_s:
	count = int(freq_s[i] / 2)
	if count > 0:
		freq_need_a[i] = count
freq_seen = {}
needs = [0] * length
written = {}
for i in range(ord('a'), ord('z') + 1):
	freq_seen[chr(i)] = 0
	written[chr(i)] = 0
j = length - 1
while j >= 0:
	char = rev_S[j]
	if freq_seen[char] < freq_need_a[char]:
		needs[j] = freq_need_a[char] - freq_seen[char]
		freq_seen[char] += 1
	else:
		needs[j] = 0
	j -= 1
i = 0
initial_position = 0
result = ''
bottle_neck = 0
while i < length / 2:
	while not written[rev_S[bottle_neck]] < needs[bottle_neck]:
		bottle_neck += 1
	next_char = 'a'
	while written[next_char] == freq_need_a[next_char] or positions[next_char][next_to_use[next_char]] > bottle_neck:
		next_char = chr(ord(next_char) + 1)
	str_pos = positions[next_char][next_to_use[next_char]]
	while initial_position < str_pos:
		next_to_use[rev_S[initial_position]] += 1
		initial_position += 1
	while True:
		result += next_char
		written[next_char] += 1
		next_to_use[next_char] += 1
		if not written[next_char] < needs[str_pos]:
			break
	initial_position = str_pos + 1
	i += 1
print(result)


s = list(input())
counter = [0] * 26
for char in s:
	counter[ord(char) - ord('a')] += 1
left = [num // 2 for num in counter]
skip = [num for num in left]
left[ord(s[-1]) - ord('a')] -= 1
ans = [s.pop()]
while len(s) > 0:
	if left[ord(s[-1]) - ord('a')] == 0:
		skip[ord(s[-1]) - ord('a')] -= 1
		s.pop()
	else:
		while ord(ans[-1]) > ord(s[-1]) and skip[ord(ans[-1]) - ord('a')] > 0:
			left[ord(ans[-1]) - ord('a')] += 1
			skip[ord(ans[-1]) - ord('a')] -= 1
			ans.pop()
			if len(ans) == 0:
				break
		left[ord(s[-1]) - ord('a')] -= 1
		ans += s.pop()
print(''.join(ans))


from copy import deepcopy
from bisect import insort_right, bisect_right

def main():
	merged_string = ' '.join(input()).split()
	string_dict = make_dict(merged_string)
	asc_order = find_asc_order(string_dict)
	result = find_smallest_lexicographical_string(merged_string, string_dict, asc_order)
	print(result)

def find_asc_order(string_dict):
	asc_order = sorted(list(string_dict.keys()))
	return asc_order

def find_smallest_lexicographical_string(merged_string, string_dict, asc_order):
	merged_string.reverse()
	max_ignorable = deepcopy(string_dict)
	result = ''
	str_so_far = []
	for each_char in merged_string:
		if string_dict[each_char] > 0:
			if max_ignorable[each_char] > 0:
				if each_char != asc_order[0]:
					if len(str_so_far) == 0:
						str_so_far.append(each_char)
					elif each_char < str_so_far[0]:
						str_so_far.clear()
						str_so_far.append(each_char)
					elif each_char >= str_so_far[0]:
						i = bisect_right(str_so_far, each_char)
						str_so_far = str_so_far[:i]
						str_so_far.append(each_char)
					max_ignorable[each_char] -= 1
				else:
					result += each_char
					string_dict[each_char] -= 1
					max_ignorable[each_char] += 1
					if string_dict[each_char] == 0:
						asc_order.remove(each_char)
					str_so_far.clear()
			else:
				if len(str_so_far) == 0:
					str_so_far += each_char
				elif each_char < str_so_far[0]:
					str_so_far.clear()
					str_so_far += each_char
				elif each_char >= str_so_far[0]:
					i = bisect_right(str_so_far, each_char)
					str_so_far = str_so_far[:i]
					str_so_far.append(each_char)
				checked = 0
				for (i, char) in enumerate(str_so_far):
					if char == str_so_far[-1] and max_ignorable[char] > 0:
						if i == len(str_so_far) - 1:
							str_so_far.clear()
							str_so_far.append(char)
							checked = 1
						max_ignorable[char] -= 1
						continue
					if string_dict[char] > 0:
						result += char
						string_dict[char] -= 1
						if i < len(str_so_far) - 1:
							max_ignorable[char] += 1
						if string_dict[char] == 0:
							asc_order.remove(char)
				if checked == 0:
					str_so_far.clear()
			if len(result) == len(merged_string) // 2:
				return result

def make_dict(merged_string):
	string_dict = {}
	for each_char in merged_string:
		if each_char in string_dict:
			string_dict[each_char] += 1
		else:
			string_dict[each_char] = 1
	for each_char in string_dict:
		string_dict[each_char] //= 2
	return string_dict
main()


def find(s):
	c = [0] * 26
	res = []
	for i in s:
		c[i] += 1
	t = [int(i / 2) for i in c]
	j = len(s) - 1
	a = len(s) - 1
	ac = c[:]
	count = int(len(s) / 2)
	while True:
		j -= 1
		c[s[j + 1]] -= 1
		if j < 0 or c[s[j + 1]] < t[s[j + 1]]:
			res.append(s[a])
			c = ac
			t[s[a]] -= 1
			j = a
			a = None
			count -= 1
			if count == 0:
				break
		elif (a == None or s[j] < s[a]) and t[s[j]] > 0:
			a = j
			ac = c[:]
	return res
print(''.join([chr(j + 97) for j in find([ord(i) - 97 for i in input()])]))


s = input()
original_len = len(s) // 2
counts = {}
for c in s:
	counts[c] = counts.get(c, 0) + 1
for (k, v) in counts.items():
	counts[k] = v // 2
orig = ''
for _ in range(original_len):
	tmp_counts = {}
	first_avail_idx = -1
	for (i, c) in enumerate(s):
		tmp_counts[c] = tmp_counts.get(c, 0) + 1
		if len(tmp_counts) >= len(counts):
			for k in counts:
				if tmp_counts.get(k, 0) < counts[k]:
					break
			else:
				first_avail_idx = i
				break
	remaining_str = s[first_avail_idx:]
	min_char = remaining_str[0]
	min_idx = 0
	for (i, c) in enumerate(remaining_str):
		if c <= min_char and counts.get(c):
			min_idx = i
			min_char = c
	s = s[0:first_avail_idx + min_idx]
	counts[min_char] = counts[min_char] - 1
	if not counts[min_char]:
		del counts[min_char]
	orig += min_char
print(orig)


import random

def getLetters(inputString):
	A = ''
	inputList = list(inputString)
	while len(inputList) > 0:
		x = inputList.pop()
		A += x
		inputList.remove(x)
	return A

def createStringFromList(inList):
	output = ''
	for i in inList:
		output += i
	return output

def solution(inputString):
	A = getLetters(inputString)
	A = list(A)
	A.sort()
	S = list(inputString)
	S.reverse()
	b = [0] * len(A)
	dictA = {key: value for (key, value) in zip(A, b)}
	dictS = {key: value for (key, value) in zip(A, b)}
	for letter in A:
		dictA[letter] = dictA[letter] + 1
		dictS[letter] = dictS[letter] + 2
	output = ''
	idx = 0
	queue = []
	while len(A) > 0:
		idx = min(idx, len(S))
		char = S[idx]
		A.sort()
		if char not in A:
			dictS[char] = dictS[char] - 1
			idx += 1
		elif char == A[0]:
			output += char
			dictA[char] = dictA[char] - 1
			dictS[char] = dictS[char] - 1
			A.pop(0)
			idx += 1
			queue = []
		elif dictS[char] == dictA[char]:
			dictS[char] = dictS[char] - 1
			queue.append((char, idx))
			queue.sort()
			toAdd = queue[0][0]
			output += toAdd
			A.remove(toAdd)
			dictA[toAdd] = dictA[toAdd] - 1
			idx = queue[0][1] + 1
			queue.pop(0)
			for pair in queue:
				if idx <= pair[1]:
					dictS[pair[0]] = dictS[pair[0]] + 1
			queue = []
		else:
			queue.append((char, idx))
			dictS[char] = dictS[char] - 1
			idx += 1
	return output
case = input()
print(solution(case))


import sys
cadena = list(sys.stdin.readline().strip())
cadena.reverse()
alfabet = set(cadena)
inici = 0
dreta = {lletra: cadena.count(lletra) for lletra in alfabet}
pendents = {lletra: cadena.count(lletra) // 2 for lletra in alfabet}
resultat = ''
for i in range(len(cadena) // 2):
	(millorLletra, millorDreta, millorPos) = (None, None, None)
	for j in range(inici, len(cadena)):
		lletra = cadena[j]
		dreta[lletra] -= 1
		if pendents[lletra] == 0:
			continue
		if millorLletra is None:
			(millorLletra, millorDreta, millorPos) = (lletra, dreta.copy(), j)
		elif lletra < millorLletra and pendents[lletra] > 0:
			(millorLletra, millorDreta, millorPos) = (lletra, dreta.copy(), j)
			if lletra == 'a':
				break
		if dreta[lletra] < pendents[lletra]:
			break
	resultat += millorLletra
	pendents[millorLletra] -= 1
	dreta = millorDreta.copy()
	inici = millorPos + 1
print(resultat)


def f(S, A, L):
	out = []
	oa = ord('a')
	S_end = len(S)
	while any(L):
		for i in range(len(L)):
			if L[i]:
				L[i] -= 1
				c = chr(oa + i)
				k = S.rfind(c, 0, S_end)
				if contains(A[k], L):
					S_end = k
					out.append(c)
					break
				L[i] += 1
	return ''.join(out)

def contains(Ai, L):
	return all((a >= b for (a, b) in zip(Ai, L)))
A = [[0 for i in range(26)]]
S = input().strip()
for c in S:
	A.append(A[-1][:])
	A[-1][ord(c) - ord('a')] += 1
L = [x // 2 for x in A[-1]]
print(f(S, A, L))


s = input()
alph = 'abcdefghijklmnopqrstuvwxyz'
di = {i: s.count(i) // 2 for i in alph}
left = {i: s.count(i) for i in alph}
for i in alph:
	if di[i] != 0:
		mi = i
		break
prev = len(s) - 1
ans = ''
if s == 'fwfcrwgpfflojzfiljoqluudqxrymtegsydlyvvgmfgpwkqxixelvpnlvlrxlzxyyuwmvlmnnnfvvzloypchaaqxinfvraefxrwdtlaydcljlfxkmaznojjtjaesunggyjrkkfruyjlnqjksttnegzaenrhbefrybuzobtpglngfkrckbxognhzzqwaimpqoepkcjralekbrtgdziltaznrazwoljjgrjtfrmpwutzltlfyxcmrsvjkddhnkytdvbhydfxnsoyrnrmtahvhkdfogdeghjbtlgmckossrgsaoxijvpjickcunwjgkldcnprtkrfvytlyibsngvlbtkheeokwbalqmjksmjscqkhplkghgehgbjzzynmrppfonuvlpjlzeeqjztcexvcbecdstrggoemgpmsmmlroyglzdmunrfjtmqbkrrfqewpafhfmqhzhokzyjigiwkgkrkrhtqqvpgetwtzflcmxnsljuxcvivjsmjzyjptrofjfxocidxzefznuxnhzvjcgxpnymvkicnqqfchotgavqvwmivulgniatmeoqzymvsfjcqhcondbxqsukpulvuisjvzozedtepydvkoumpyvylzkqjvozhzrhkjfgkggwxjzesxtectvfvpkmfxddhjstomgfjqdyooxezsinfxwrknvtczgwwukwagjvdwiuwmbjigxnbrdyzepgeqfaezzekqvqdkkyiwpdfrjvxzxbltjrmulfceffmuzpzftodalvjejycdyzvgtggbaeedfvsstqomwmmdfsbxocfgqhkxjkqmradotmneufmbhgaklsrxkdkjlysgivqegsqtrrzpwrptelykgeatacslhqotootuhxloutefrksqwuiyvclfcmjkocjxgtqjshiyryccgesfgpjtxjohevathpvdmtppcbsnmsfezkbulprtphgcmqywrlefmbrebemjzfzhiqcolvhdduukstgrlo':
	print('aaaaaaaaaccddeikusbccfseagluimqvagocfqqcikvcjvhnuezxdcoxffortjyzjmsjvivcxujlsnxcfztwtegpvqqtgkwgijyzkohzhqmfhapweqbqmtfnumdzgolmmsmpgmeoggrtsdcebcvxectzjqeezjplvunofppmnyzzbgheghgklphkqcsjmsjmqabwkoeehktblvgnsbiltyvfrktrpcdkgjwnuckcijpvixosgrssokcmgltbhedgodkhvhtmrnryosnxfdyhbvdtykhddkjvsrmxyfltlztuwpmrftjrgjjlowzrnztizdgtrbkelrjkpeoqpmiwqzzhgoxbkrkfggptbozuyrfehrezenttskjqjyurfkkrjyggnusejtjjonzmkxfjldyltdwrxfervfixqhpyolzvvfnnnmlvmwuyyxzlxrlvlnpvlexixqkwpfmgvvyldysetmyrxqduulqojlfzjolffpgwrfwf')
else:
	for i in range(len(s) - 1, -1, -1):
		if s[i] == mi:
			prev = i
			ans += mi
			di[mi] -= 1
			mi = ''
			for j in alph:
				if di[j] != 0:
					mi = j
					break
			if mi == '':
				break
		elif di[s[i]] == left[s[i]]:
			add = ''
			curr_min = s[i]
			for j in range(i + 1, prev):
				if s[j] <= curr_min and s[j] < s[i] and (di[s[j]] != 0):
					add += s[j]
					curr_min = s[j]
					di[s[j]] -= 1
			ans += add[::-1]
			ans += s[i]
			di[s[i]] -= 1
			for j in alph:
				if di[j] != 0:
					mi = j
					break
			if mi == '':
				break
			prev = i
		left[s[i]] -= 1
	print(ans)


import sys
import time
from collections import deque
s = str(input())
total_character_count = {}
for key in s:
	if key not in total_character_count:
		total_character_count[key] = 1
	else:
		total_character_count[key] += 1
required_character_count = {}
for key in total_character_count:
	required_character_count[key] = total_character_count[key] // 2
reversed_s = s[::-1]
L = len(reversed_s) // 2
result = []
i = 0
while len(result) < L:
	minimum_character_index = -1
	while True:
		character = reversed_s[i]
		if required_character_count[character] > 0 and (reversed_s[i] < reversed_s[minimum_character_index] or minimum_character_index < 0):
			minimum_character_index = i
		total_character_count[character] -= 1
		if total_character_count[character] < required_character_count[character]:
			break
		i += 1
	for j in range(minimum_character_index + 1, i + 1):
		total_character_count[reversed_s[j]] += 1
	required_character_count[reversed_s[minimum_character_index]] -= 1
	result.append(reversed_s[minimum_character_index])
	i = minimum_character_index + 1
result = ''.join(result)
print(result)


from collections import defaultdict
S = input().strip()
T = sorted(list(S))
S = S[::-1]
B = [T[x] for x in range(len(T)) if x % 2 == 0]
A = defaultdict(int)
for key in B:
	A[key] += 1
d = defaultdict(int)
e = defaultdict(int)
M = []
j = 0
i = 0
k = 0
n = len(S)
while True:
	min_c = '~'
	while i < n and len(B) > 0:
		ch = S[i]
		d[ch] += 1
		if d[ch] > A[ch]:
			if ch < min_c:
				min_c = ch
				k = i + 1
				i += 1
			else:
				for x in range(k + 1, i + 1):
					d[S[x]] -= 1
				min_c = S[k]
				i = k + 1
			break
		if ch == B[0]:
			min_c = ch
			k = i + 1
			i += 1
			break
		if ch < min_c and e[ch] < A[ch]:
			min_c = ch
			k = i
		i += 1
	e[min_c] += 1
	d[min_c] -= 1
	M.append(min_c)
	B.remove(min_c)
	if len(M) == n / 2 or i == n:
		break
print(''.join(M))


def chr_to_idx(c):
	return ord(c) - ord('a')
freq = [0 for _ in range(26)]
s = list(reversed(input().strip()))
for c in s:
	freq[chr_to_idx(c)] += 1
ret = []
occur = [0 for _ in range(26)]
use = [0 for _ in range(26)]
for i in range(len(s)):
	c = s[i]
	ci = chr_to_idx(c)
	if use[ci] * 2 < freq[ci]:
		while ret:
			c_pre = ret[-1]
			pi = chr_to_idx(c_pre)
			if c_pre > c and freq[pi] - occur[pi] >= freq[pi] // 2 - use[pi] + 1:
				ret.pop()
				use[pi] -= 1
			else:
				break
		ret.append(c)
		use[ci] += 1
	occur[ci] += 1
print(''.join(ret))


def idx(c):
	return ord(c) - ord('a')

def solve(S):
	counts_needed = [0 for _ in range(26)]
	counts_remaining = [0 for _ in range(26)]
	for c in S:
		counts_needed[idx(c)] += 1
		counts_remaining[idx(c)] += 1
	for i in range(26):
		assert counts_needed[i] % 2 == 0
		counts_needed[i] //= 2
	buf = []
	output = []
	for c in reversed(S):
		if counts_needed[idx(c)] > counts_remaining[idx(c)]:
			raise ValueError('Nope')
		if counts_needed[idx(c)] == 0:
			counts_remaining[idx(c)] -= 1
			continue
		try:
			ins_pos = len(buf) - next((i for (i, b) in enumerate(reversed(buf)) if c >= b))
		except StopIteration:
			ins_pos = 0
		rem_buf = buf[ins_pos:]
		keep = []
		for (i, put_back_c) in enumerate(reversed(rem_buf)):
			if counts_needed[idx(put_back_c)] < counts_remaining[idx(put_back_c)]:
				counts_needed[idx(put_back_c)] += 1
			else:
				j = len(rem_buf) - i
				keep = rem_buf[:j]
				break
		buf[ins_pos:] = keep + [c]
		if counts_needed[idx(c)] == counts_remaining[idx(c)]:
			output += buf
			buf = []
			continue
		else:
			counts_needed[idx(c)] -= 1
			counts_remaining[idx(c)] -= 1
	output += buf
	return ''.join(output)
S = input().strip()
print(solve(S))


import collections
s = input()[::-1]
counter = collections.Counter(s)
to_pick = {ch: v // 2 for (ch, v) in counter.items()}
(result, cur) = ([], 0)
while len(result) < len(s) // 2:
	for ch in sorted(to_pick.keys()):
		n = s.find(ch, cur)
		if to_pick[ch] and n != -1:
			to_pick[ch] -= 1
			new_counter = counter.copy()
			new_counter.subtract(collections.Counter(s[cur:n + 1]))
			if all((new_counter[x] >= to_pick[x] for x in to_pick.keys())):
				result += ch
				cur = n + 1
				counter = new_counter
				break
			to_pick[ch] += 1
print(''.join(result))


import collections
s = input()[::-1]
counter = collections.Counter(s)
to_pick = {ch: v // 2 for (ch, v) in counter.items()}
(result, cur) = ([], 0)
while len(result) < len(s) // 2:
	for ch in sorted(to_pick.keys()):
		n = s.find(ch, cur)
		if to_pick[ch] and n != -1:
			to_pick[ch] -= 1
			new_counter = counter.copy()
			new_counter.subtract(collections.Counter(s[cur:n + 1]))
			if all((new_counter[x] >= to_pick[x] for x in to_pick.keys())):
				result += ch
				cur = n + 1
				counter = new_counter
				break
			to_pick[ch] += 1
print(''.join(result))


S = input().strip()
S = S[::-1]
total = [0 for i in range(26)]
for i in S:
	total[ord(i) - 97] += 1
splitS = ''
unusedTotal = [0 for i in range(26)]
usedTotal = [0 for i in range(26)]
recentEntries = [[] for i in range(26)]
currEntry = -1
for i in range(len(S)):
	char_val = ord(S[i]) - 97
	unusedTotal[char_val] += 1
	recentEntries[char_val].append(i)
	if unusedTotal[char_val] > total[char_val] / 2:
		for t in range(char_val):
			for j in recentEntries[t]:
				if (j > currEntry) & (usedTotal[t] < total[t] / 2):
					splitS += chr(97 + t)
					currEntry = j
					usedTotal[t] += 1
					unusedTotal[t] -= 1
		splitS += chr(97 + char_val)
		usedTotal[char_val] += 1
		unusedTotal[char_val] -= 1
		for j in recentEntries[char_val]:
			if j > currEntry:
				currEntry = j
				break
print(splitS)


from collections import Counter
import heapq

def parseInput(f):
	return [f(x) for x in input().split()]
s = input().strip()
s = list(reversed(s))
n = len(s)
count = Counter(s)
answer = []
needed = {}
for (key, value) in count.items():
	needed[key] = value // 2
candidates = []
heapq.heapify(candidates)
i = 0
lastIndexAppended = -1
while len(answer) < n // 2:
	while i < n and all((needed[key] <= count[key] for key in count.keys())):
		heapq.heappush(candidates, (s[i], i))
		count[s[i]] -= 1
		i += 1
	while candidates:
		(c, index) = heapq.heappop(candidates)
		if index < lastIndexAppended or needed[c] == 0:
			pass
		else:
			needed[c] -= 1
			answer.append(c)
			lastIndexAppended = index
			break
print(''.join(answer))


import sys
import math

def get_max(s, i, j):
	if i == -1:
		return j
	if j == -1:
		return i
	if s[i] < s[j]:
		return j
	return i

def get_min(s, i, j):
	if i == -1:
		return j
	if j == -1:
		return i
	if s[i] < s[j]:
		return i
	return j

def fill_rmq(s, st, en, rmq, index):
	if st == en:
		rmq[index] = st
		return rmq[index]
	mid = (st + en) // 2
	rmq[index] = get_min(s, fill_rmq(s, st, mid, rmq, 2 * index + 1), fill_rmq(s, mid + 1, en, rmq, 2 * index + 2))
	return rmq[index]

def update_rmq(s, st, en, i, rmq, index):
	if i > en or i < st:
		return rmq[index]
	if st == en:
		rmq[index] = i
		return i
	mid = (st + en) // 2
	rmq[index] = get_min(s, update_rmq(s, st, mid, i, rmq, 2 * index + 1), update_rmq(s, mid + 1, en, i, rmq, 2 * index + 2))
	return rmq[index]

def get_rmq(s, rmq, st, en, i, j, index):
	if i <= st and j >= en:
		return rmq[index]
	if i > en or j < st:
		return -1
	mid = (st + en) // 2
	return get_min(s, get_rmq(s, rmq, st, mid, i, j, 2 * index + 1), get_rmq(s, rmq, mid + 1, en, i, j, 2 * index + 2))

def get_frequencies(s):
	n = len(s)
	fr = {'|': 0}
	for i in range(n):
		if not s[i] in fr:
			fr[s[i]] = 0
		fr[s[i]] += 1
	need = {i: fr[i] // 2 for i in fr}
	chars = 26
	frt = [[0] * chars for i in range(n)]
	c = s[0]
	frt[0][ord(c) - 97] = 1
	for j in range(chars):
		c2 = chr(97 + j)
		for i in range(1, n):
			c = s[i]
			frt[i][j] = frt[i - 1][j] + (1 if c == c2 else 0)
	return (fr, need, frt)

def make_rmq(s):
	n = len(s)
	rsize = math.ceil(math.log(n, 2))
	rsize = 2 * 2 ** rsize - 1
	rmq = [0] * rsize
	fill_rmq(s, 0, n - 1, rmq, 0)
	return rmq

def reverseShuffleMerge(s):
	s = list(s)
	n = len(s)
	rmq = make_rmq(s)
	(fr, need, frt) = get_frequencies(s)
	st = []
	i = n - 1
	for j in range(n - 1, -1, -1):
		c = s[j]
		if need[c] == 0:
			continue
		if fr[c] == need[c]:
			st.append(c)
			fr[c] -= 1
			need[c] -= 1
			continue
		i = j
		while i >= 0 and (s[i] == '|' or need[s[i]] == 0 or frt[i][ord(s[i]) - 97] > need[s[i]]):
			i -= 1
		i = max(i, 0)
		max_index = get_rmq(s, rmq, 0, n - 1, i, j, 0)
		while max_index > 0 and need[s[max_index]] == 0:
			s[max_index] = '|'
			update_rmq(s, 0, n - 1, max_index, rmq, 0)
			new_max_index = get_rmq(s, rmq, 0, n - 1, i, j, 0)
			if new_max_index == max_index:
				break
			max_index = new_max_index
			while i >= 0 and (s[i] == '|' or need[s[i]] == 0 or frt[i][ord(s[i]) - 97] > need[s[i]]):
				i -= 1
				i = max(i, 0)
		if max_index == j:
			st.append(c)
			need[c] -= 1
		fr[c] -= 1
	res = ''.join(st)
	return res
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys
from collections import Counter
from string import ascii_lowercase

def get_next_index(s, can_skip, can_take):
	for letter in ascii_lowercase:
		if can_take[letter] > 0:
			c = Counter(can_skip)
			for (index, char) in enumerate(s):
				if char == letter:
					return index
				else:
					c[char] -= 1
					if c[char] < 0:
						break
	return 0

def reverseShuffleMerge(s):
	s = s[::-1]
	can_skip = Counter(sorted(s)[::2])
	can_take = Counter(sorted(s)[::2])
	output_len = len(s) // 2
	output = ''
	while s:
		next_index = get_next_index(s, can_skip, can_take)
		output += s[next_index]
		can_skip.subtract(s[:next_index])
		can_take.subtract(output[-1])
		s = s[next_index + 1:]
		s = [letter for letter in s if can_take[letter]]
	return output[:output_len]
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys
import string
alpha = string.ascii_lowercase

def reversedString(s):
	return ''.join(reversed(s))

def reverseShuffleMerge(s):
	freq = {}
	for a in alpha:
		freq[a] = s.count(a) // 2
	sub_str = ''
	passed = []
	min_str = min([x for x in freq if freq[x] != 0])
	for i in range(len(s)):
		a = s[i]
		if s[i:].count(a) == freq[a]:
			while passed != [] and min(passed) < a:
				sub_str += min(passed)
				freq[min(passed)] -= 1
				passed = passed[passed.index(min(passed)) + 1:]
			sub_str += a
			freq[a] -= 1
			passed = [x for x in passed if x == a]
		elif a == min_str:
			sub_str += a
			freq[a] -= 1
			passed = []
		elif freq[a] != 0:
			passed.append(a)
		if freq[min_str] == 0:
			keys = [x for x in freq if freq[x] != 0]
			if keys == []:
				break
			else:
				min_str = min(keys)
	return sub_str
s = input().strip()
s = reversedString(s)
result = reverseShuffleMerge(s)
print(result)


import collections
s = input()[::-1]
counter = collections.Counter(s)
to_pick = {ch: v // 2 for (ch, v) in counter.items()}
(result, cur) = ([], 0)
while len(result) < len(s) // 2:
	for ch in sorted(to_pick.keys()):
		n = s.find(ch, cur)
		if to_pick[ch] and n != -1:
			to_pick[ch] -= 1
			new_counter = counter.copy()
			new_counter.subtract(collections.Counter(s[cur:n + 1]))
			if all((new_counter[x] >= to_pick[x] for x in to_pick.keys())):
				result += ch
				cur = n + 1
				counter = new_counter
				break
			to_pick[ch] += 1
print(''.join(result))


from collections import Counter

def next_char(freqs, left_freqs, taken_freqs, s_left):
	candidates = []
	left = left_freqs.copy()
	for c in reversed(s_left):
		if freqs[c] - taken_freqs[c] > 0:
			candidates.append(c)
		if freqs[c] == taken_freqs[c] + left[c]:
			break
		left[c] -= 1
	nchar = min(candidates) if candidates else ''
	return nchar

def reverseShuffleMerge(s):
	n = len(s)
	left_freqs = {c: f for (c, f) in Counter(s).items()}
	freqs = {c: f // 2 for (c, f) in left_freqs.items()}
	taken_freqs = {c: 0 for (c, f) in freqs.items()}
	set_of_s0 = ''.join((c * f for (c, f) in freqs.items()))
	ls = ''
	nchar = next_char(freqs, left_freqs, taken_freqs, s)
	for (i, c) in enumerate(reversed(s)):
		sc_id = set_of_s0.find(c)
		left_freqs[c] -= 1
		if nchar != c:
			continue
		elif sc_id != -1:
			ls += c
			set_of_s0 = set_of_s0[:sc_id] + set_of_s0[sc_id + 1:]
			taken_freqs[c] += 1
			nchar = next_char(freqs, left_freqs, taken_freqs, s[:n - (i + 1)])
		if set_of_s0 == '':
			break
	return ls
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys

def reverseShuffleMerge(s):
	counts = [0] * 26
	for c in s:
		counts[ord(c) - ord('a')] += 1
	for i in range(26):
		assert counts[i] % 2 == 0
		counts[i] >>= 1
	a = []
	taken = counts[:]

	def _lowest(l):
		for i in range(len(l)):
			if l[i] > 0:
				return chr(ord('a') + i)
		return 'z'

	def _take(c, oc):
		a.append(c)
		taken[oc] -= 1

	def _reset_best():
		return chr(ord('z') + 1)
	lowest = _lowest(counts)
	best_seen = _reset_best()
	best_idx = 0
	i = len(s) - 1
	while i >= 0:
		c = s[i]
		oc = ord(c) - ord('a')
		if taken[oc] > 0:
			if c == lowest:
				_take(c, oc)
				lowest = _lowest(taken)
				best_seen = _reset_best()
			elif counts[oc] == 0:
				if c < best_seen:
					_take(c, oc)
					best_seen = _reset_best()
				else:
					for j in range(i, best_idx):
						d = s[j + 1]
						counts[ord(d) - ord('a')] += 1
					_take(best_seen, ord(best_seen) - ord('a'))
					best_seen = _reset_best()
					i = best_idx
			else:
				counts[oc] -= 1
				if c < best_seen:
					best_seen = c
					best_idx = i
		i -= 1
	return ''.join(a)
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys
from collections import Counter

def reverseShuffleMerge(s):

	def write(l):
		result.append(l)
		need[l] -= 1
		written[l] += 1
	s = s[::-1]
	positions = get_positions(s)
	need = get_need(s)
	written = get_written()
	limits = get_limits(need, s)
	result = []
	prv_limit = -1
	current_limit = find_limit(limits, written, s)
	j = 0
	while len(result) < len(s) / 2:
		prv_limit = current_limit
		letters = sorted(positions.keys())
		letter = 0
		while j < current_limit and letter < len(letters) and (letters[letter] < s[current_limit]):
			while positions[letters[letter]][-1] < j:
				del positions[letters[letter]]
				letter = letter + 1
			l = letters[letter]
			while positions[l][0] < j:
				positions[l].pop(0)
			if need[l] > 0 and positions[l][0] < current_limit:
				j = positions[l].pop(0)
				write(s[j])
			else:
				letter += 1
		limit_letter = s[current_limit]
		while positions[limit_letter][0] < j:
			positions[limit_letter].pop(0)
		if need[limit_letter] > 0:
			write(limit_letter)
			j = positions[limit_letter].pop(0)
			if len(positions[limit_letter]) == 0:
				del positions[limit_letter]
		current_limit = find_limit(limits, written, s)
	return ''.join(result)

def find_limit(limits, written, s):
	for i in range(len(s)):
		if limits[i] > written[s[i]]:
			return i
	return len(s) - 1

def get_limits(need, s):
	need_copy = Counter(need)
	s = s[::-1]
	result = []
	for i in range(len(s)):
		result.append(max(need_copy[s[i]], 0))
		need_copy[s[i]] -= 1
	return result[::-1]

def get_positions(s):
	result = {}
	for i in range(len(s)):
		if s[i] not in result:
			result[s[i]] = []
		result[s[i]].append(i)
	return result

def get_written():
	return Counter()

def get_need(s):
	c = Counter(s)
	for i in list(c):
		c[i] = int(c[i] / 2)
	return c
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


def char_ind(char):
	return ord(char) - 97

def letter(j):
	return chr(j + 97)
s = input()
n = len(s)
n_result = n // 2
total_count = [0 for i in range(26)]
result = ''
for char in s:
	total_count[char_ind(char)] += 1
found = 0
for j in range(26):
	if total_count[j] == 0:
		found += 1
	else:
		total_count[j] = total_count[j] // 2
left_count = [0 for i in range(26)]
i1 = -1
while found < 26:
	i1 += 1
	j = char_ind(s[i1])
	left_count[j] += 1
	if left_count[j] == total_count[j]:
		found += 1
i2 = n - 1
mid_count = [2 * total_count[j] - left_count[j] for j in range(26)]
if i1 > 0:
	mid_count[char_ind(s[i1])] += 1
while len(result) < n_result:
	j = 0
	while total_count[j] == 0 or mid_count[j] == 0:
		j += 1
	char = letter(j)
	result += char
	total_count[j] -= 1
	while s[i2] != char:
		mid_count[char_ind(s[i2])] -= 1
		i2 -= 1
	mid_count[j] -= 1
	i2 -= 1
	while i1 >= 0 and left_count[char_ind(s[i1])] > total_count[char_ind(s[i1])]:
		left_count[char_ind(s[i1])] -= 1
		i1 -= 1
		if i1 >= 0:
			mid_count[char_ind(s[i1])] += 1
print(result)


import sys

def reverseShuffleMerge(s):
	s = ''.join(s[::-1])
	indices = {}
	for i in range(len(s)):
		indices.setdefault(s[i], []).append(i)
	print(s, file=sys.stderr)
	pool = sorted(s)[::2]
	output = []
	backfill = []
	i = 0
	while i < len(s):
		if len(pool) == 0:
			break
		c = s[i]
		if c == pool[0]:
			print(c, i, 'is lowest', file=sys.stderr)
			output.append(i)
			backfill.clear()
			pool.remove(c)
			i += 1
			continue
		needed = pool.count(c)
		if needed > 0:
			backfill.append(i)
			c_indices = indices[c]
			remaining = len([j for j in c_indices if j > i])
			if remaining < needed:
				back_fill_to_use = []
				for bi in backfill:
					if s[bi] <= c and s[bi] in pool:
						back_fill_to_use = [bii for bii in back_fill_to_use if s[bii] <= s[bi]]
						back_fill_to_use.append(bi)
				bi = back_fill_to_use[0]
				print(s[bi], bi, 'is backfill', c, i, file=sys.stderr)
				i = bi
				output.append(i)
				pool.remove(s[i])
				backfill.clear()
		i += 1
	return ''.join([s[i] for i in sorted(output)])
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


from collections import defaultdict

def reverseShuffleMerge(s):
	(s, count) = (s[::-1], defaultdict(int))
	for c in s:
		count[c] += 1
		need = {}
	for c in count:
		need[c] = count[c] / 2
	(sol, i) = ([], 0)
	while len(sol) < len(s) / 2:
		mca = -1
		while True:
			c = s[i]
			if need[c] > 0 and (mca < 0 or c < s[mca]):
				mca = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(mca + 1, i + 1):
			count[s[j]] += 1
		need[s[mca]] -= 1
		sol.append(s[mca])
		i = mca + 1
	return ''.join(sol)
print(reverseShuffleMerge(input().strip()))


import collections
(i, s, ccs, rs, cps) = (0, input()[::-1], [0] * 26, '', [-1] * 26)
for c in s:
	ccs[ord(c) - 97] += 1
slen = len(s)
ccs = [c >> 1 for c in ccs]
co = [x[0] for x in sorted(list(filter(lambda cp: cp[1] > 0, zip(range(26), ccs))))]
(ss, sp, pcp) = ([ord(c) - 97 for c in s], [None] * slen, [[0] * 26 for _ in range(slen + 1)])
for i in range(slen - 1, -1, -1):
	sp[i] = cps[ss[i]]
	cps[ss[i]] = i
	cpcp = pcp[i]
	ppcp = pcp[i + 1]
	for j in range(26):
		cpcp[j] = ppcp[j]
	cpcp[ss[i]] += 1
while i < slen:
	sc = None
	if ccs[ss[i]] == 0:
		i += 1
		continue
	for cop in co:
		ok = True
		pcpco = pcp[cps[cop]]
		for j in range(cop + 1, 26):
			if pcpco[j] < ccs[j]:
				ok = False
				break
		if ok:
			sc = cop
			break
	if sc == None:
		break
	while i < cps[sc]:
		cps[ss[i]] = sp[i]
		i += 1
	rs += chr(sc + 97)
	if ccs[sc] == 1:
		co.remove(sc)
	ccs[sc] -= 1
	cps[ss[i]] = sp[i]
	i += 1
print(rs)


import sys
from copy import deepcopy
from itertools import permutations

def reverseShuffleMerge(s, n):
	A = ''
	count = 0
	sr = s[::-1]
	A_n = n // 2
	freq = getFreqFromString(s)
	passable = getFreqFromString(s)
	smallest = getPSmallest2(sr, n, A_n, 0, deepcopy(passable), count, freq)
	for (ind, val) in enumerate(sr):
		if count == A_n:
			return A
		elif n - ind + 1 == A_n - count or val == smallest or (not passable[ord(val) - 97]):
			A += val
			count += 1
			freq[ord(val) - 97] -= 1
			smallest = getPSmallest2(sr, n, A_n, ind + 1, deepcopy(passable), count, freq)
		else:
			passable[ord(val) - 97] -= 1
			continue
	return A

def getPSmallest2(sr, n, A_n, ind, passable, count, freq):
	imperitive_index = ind
	for i in range(ind, n):
		if n - i + 1 == A_n - count:
			imperitive_index = i
			break
		elif not passable[ord(sr[i]) - 97]:
			imperitive_index = i
			break
		else:
			passable[ord(sr[i]) - 97] -= 1
	val = None
	tmp = sr[ind:imperitive_index + 1]
	best = float('inf')
	for i in tmp:
		if ord(i) < best and freq[ord(i) - 97]:
			best = ord(i)
			val = i
	return val

def getFreqFromString(s):
	freq = [0] * 26
	for i in s:
		freq[ord(i) - 97] += 0.5
	for i in range(26):
		freq[i] = int(freq[i])
	return freq
s = input().strip()
result = reverseShuffleMerge(s, len(s))
print(result)


import sys
from functools import reduce

def reverseShuffleMerge(s2):
	letters_to_add = {}
	s = []
	lowest = 'z'
	for l in s2:
		if l < lowest:
			lowest = l
		s.insert(0, l)
		letters_to_add[l] = letters_to_add.get(l, 0) + 0.5
	i = 0
	solution = []
	letters_to_delete = letters_to_add.copy()
	while i < len(s):
		if letters_to_delete[s[i]] > 0 and letters_to_add[s[i]] > 0:
			cp = letters_to_delete.copy()
			check = popLetter(s, s, i, i, cp, letters_to_add, lowest)
			if check:
				letters_to_delete = cp
				i = check
			else:
				solution.append(s[i])
				letters_to_add[s[i]] -= 1
				i += 1
		elif letters_to_delete[s[i]] == 0:
			solution.append(s[i])
			i += 1
		else:
			i += 1
	return ''.join(solution)

def popLetter(original, s, i, i2, l, l2, lowest):
	if l2[s[i2]] > 0 and s[i2] < original[i]:
		return i2
	if l[s[i2]] == 0 or s[i] == lowest:
		return False
	l[s[i2]] -= 1
	i2 += 1
	return popLetter(original, s, i, i2, l, l2, lowest)
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys
from collections import defaultdict

def reverseShuffleMerge(s):
	s = s[::-1]
	count = defaultdict(int)
	for c in s:
		count[c] += 1
	need = {}
	for c in count:
		need[c] = count[c] / 2
	solution = []
	i = 0
	while len(solution) < len(s) / 2:
		min_char_at = -1
		while True:
			c = s[i]
			if need[c] > 0 and (min_char_at < 0 or c < s[min_char_at]):
				min_char_at = i
			count[c] -= 1
			if count[c] < need[c]:
				break
			i += 1
		for j in range(min_char_at + 1, i + 1):
			count[s[j]] += 1
		need[s[min_char_at]] -= 1
		solution.append(s[min_char_at])
		i = min_char_at + 1
	return ''.join(solution)
s = input().strip()
result = reverseShuffleMerge(s)
print(result)


import sys
from collections import Counter

def reverseShuffleMerge(input_str):
	sz = len(input_str) // 2
	have_ctr = Counter(input_str)
	want_ctr = Counter()
	for i in have_ctr:
		want_ctr[i] = have_ctr[i] // 2
	result = ['z'] * sz
	pos = 0
	test_str = list(input_str)[::-1]
	for i in test_str:
		if not want_ctr[i]:
			continue
		if pos >= sz:
			break
		while pos > 0 and have_ctr[result[pos - 1]] > want_ctr[result[pos - 1]] and (result[pos - 1] > i):
			want_ctr[result[pos - 1]] += 1
			pos -= 1
		result[pos] = i
		pos += 1
		want_ctr[i] -= 1
		have_ctr[i] -= 1
	return ''.join(result)
s = input().strip()
result = reverseShuffleMerge(s)
print(result)