#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=1e6+5;
string s;
int to[N];
ull pw[N];
struct node{
    int nxt,sm;
}p[N];
struct nodes{
    int x,lth;
    ull hs;
    friend bool operator<(nodes a,nodes b){
        if(a.hs==b.hs)return 0;
        int x=a.x,y=b.x;
        for(;;x=p[x].nxt,y=p[y].nxt){
            if(p[x].sm!=p[y].sm)return p[x].sm<p[y].sm;
            if(!p[y].nxt)return 0;
            if(!p[x].nxt)return 1;
        }
    }    
};
multiset<nodes>q;
signed main(){
    cin>>s;
    pw[0]=1;
    for(int i=1;i<=s.size();i++)pw[i]=pw[i-1]*131;
    for(int i=0;i<s.size();i++){
        p[i+1].sm=s[i]-'a';
        to[i+1]=i+1;
        q.insert({i+1,1,p[i+1].sm});
    }
    while(q.size()>1){
        auto a=(*q.begin()),b=(*(--q.end()));
        p[to[a.x]].nxt=b.x;
        to[a.x]=to[b.x];
        q.erase(q.begin());q.erase(--q.end());
        q.insert({a.x,a.lth+b.lth,a.hs*pw[b.lth]+b.hs});
    }
    int i=(*q.begin()).x;
    for(;i;i=p[i].nxt){
        putchar(p[i].sm+'a');
    }
}