#include <stdio.h>

char *reverseShuffleMerge(char *s, char *result, int n) {
    int j = 0;
    result[n] = '\0';
    int available[26] = {}, required[26];
    for (int i = 0; s[i]; ++i) ++available[s[i] - 'a'];
    for (int i = 0; i < 26; ++i) required[i] = available[i] >> 1;
    for (int i = (n << 1) - 1; i >= 0; --i) {
        char c = s[i];
        int t = c - 'a';
        if (!required[t]) {
            --available[t];
            continue;
        }
        while (j > 0 && c < result[j-1] && 
          available[result[j-1] - 'a'] > required[result[j-1] - 'a']) {
            ++required[result[--j] - 'a'];
        }
        result[j++] = c;
        --required[t];
        --available[t];
        if (j == n) break;
    }
    return result;
}
int main() {
    char s[10001];
    scanf("%s", s);
    int n = strlen(s) >> 1;
    char result[n+1];
    printf("%s\n", reverseShuffleMerge(s, result, n));
    return 0;
}

def reverseShuffleMerge(s):
    # Write your code here
    
    stashed_dic = Counter(s)
    # the intial requirments for each char
    required_dic = {c:math.ceil(v/2) for c,v in stashed_dic.items()}
    
    result = []
    
    for c in reversed(s):
        stashed_dic[c] -= 1
        if required_dic[c] <= 0:
            continue
        # deal with the pop    
        while result:
            last_c = result[-1]
            if (c < last_c ) and (stashed_dic[last_c] >= required_dic[last_c] + 1):
                result.pop()
                required_dic[last_c] += 1 
            else:
                break
        result.append(c)
        required_dic[c] -= 1
        
    return  "".join(result)   

from collections import Counter

def reverseShuffleMerge(s):
    char_counts = Counter(s)
    required = Counter()
    for key, value in char_counts.items():
        required[key] = value // 2
    last_char = s[-1]
    char_counts[last_char] -= 1
    required[last_char] -= 1
    result = [last_char]
    for i in range(len(s)-2, -1, -1):
        char = s[i]
        char_counts[char] -= 1
        if not required[char]:
            pass
        elif (not result) or (char >= result[-1]):
            result.append(char)
            required[char] -= 1
        else:
            while result and char < result[-1] and char_counts[result[-1]] >= required[result[-1]] +1:
                old_char = result.pop(-1)
                required[old_char] += 1
            result.append(char)
            required[char] -= 1
    return "".join(result)