best cow line timer 1s memory 128MB

농부 창호는 자신이 기르고 있는 N(1≤N≤2,000)마리의 소들데리고 “올해의 농부” 선발대회에서 상을 차지하고자 한다. 

이 대회에서 모든 농부의 소들은 한 줄로 무리지어서 채점관을 지나가게 된다.

대회 주최 측은 이번 대회에서 다음과 같은 등록 규정을 제시했다: 등록을 위해서 무리를 지어서 움직일 소들의 영문 이름의 첫 글자를 딴 문자열로 등록을 하게 된다

(예로 들어 창호가 Bessie, Sylvia, Dora라는 소들을 이 순서대로 등록하게 되면 BSD로 등록을 하면 된다.) 

등록이 마감되면 채점은 등록된 문자열의 오름차순 순으로 채점을 받게 된다.

창호는 올해 너무 바빠서 급히 농장으로 돌아가야 해서 최대한 빨리 채점을 받고자한다(사전 순으로 가장 빠른 문자열로 등록을 하면 된다). 

따라서 창호는 소들을 다시 재배치를 해서 최대한 빠르게 채점을 받고자 한다.

창호는 지금 소들이 줄 서 있지 않은 다른 곳에 새로운 줄을 긋는다. 

그 다음 현재 소들이 서 있는 줄의 맨 처음이나 마지막에 위치한 소들 중 하나를 데리고 새로운 줄에 배치한다. 

그 다음 위와 같은 동작을 반복하여 N마리의 소를 배치한다.

처음에 등록하고자 했던 소들의 이름의 첫 글자에 대한 문자열이 들어 왔을 때, 

사전순으로 가장 빠르고 가능한 문자열을 찾는 프로그램을 작성하라.