#include<stdio.h>
#include<string.h>
char s[51];
char now[51];
int sn;
int cnt[30];
bool dfs(int cur,bool origin)
{
if(cur == sn)
{
now[cur] = '\0';
if(origin) return false;
else return true; //find the next one
}
char ch = origin?s[cur]:'a';
for(; ch <= 'z'; ++ch)
{
if(cnt[ch-'a'])
{
cnt[ch-'a']--;
now[cur] = ch;
bool res = dfs(cur+1,origin && ch==s[cur]);
//if ch!=s[cur], then arrange the remaining(unused) alphas from 'a' to 'z'
if(res)
return true;
else
{
cnt[ch-'a']++;
}
}
}
return false;
}
int main()
{
while(scanf("%s",s) == 1)
{
if(!strcmp(s,"#")) break;
memset(cnt,0,sizeof(cnt));
sn = strlen(s);
for(int i=0; i < sn; ++i)
{
cnt[s[i]-'a']++;
}
dfs(0,true);
printf("%s\n",now);
}
}
