[BOJ] 16719

import sys
sys.stdin.readline
name=list(input()) #name을 입력받아서 list로 쪼개는 과정
result=['']*len(name) #name길이 만큼의 알파벳 넣을 공간 생성

def solve(name,pivot):
    if not name:
        return # name이 empty, 즉 정렬이 끝났으면 return
    alpha=min(name) #사전에서 가장 빠른 alphabet 탐색
    idx=name.index(alpha) # 그 alphabet의 index 탐색
    result[pivot+idx]=alpha # 공란이었던 result배열에 alphabet 대입
    print("".join(result)) 
    solve(name[idx+1:],pivot+idx+1) # alphabet 기준으로 뒤 먼저 탐색
    solve(name[:idx],pivot) # alphabet 기준으로 앞 탐색

solve(name,0)