def reverseShuffleMerge(s):
    from collections import Counter

    rem, out = Counter(s), ''
    reqd = {k: v // 2 for k, v in rem.items()}

    for curr in reversed(s):    # iterate backwards
        if reqd[curr]:              # if curr is still reqd
            while out and (prev := out[-1]) > curr and rem[prev] > reqd[prev]:
                reqd[prev] += 1         # if prev is bigger and more remain
                out = out[:-1]          # than reqd, put prev back in reqd
            reqd[curr] -= 1         # take curr out of reqd
            out += curr
        rem[curr] -= 1          # take curr out of remain

    return out

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