알파카는 언제나 신비롭다. 알파카들이 사용하는 문장들도 매우 신비한데, 알파카들의 문장에서 등장하는 알파벳들은 앞에서부터 읽으나 뒤에서부터 읽으나 항상 똑같다. 알파카 문장의 예로는 'Do geese see god?' (dogeeseseegod), 'Amore, Roma.', 'Rise to vote, sir.' 등이 있다.

경현이는 알파카를 매우 좋아하기 때문에 알파카들의 서식지에서 빈둥빈둥대면서 알파카들의 소설책을 읽고 있었다.

그러던 어느 날, 알파카들이 땅을 파고 있었다. 궁금한 경현이가 구덩이를 보았더니 석판에 고대 알파카 문장이 적혀있었다. 이 문장은 약 46억 년 전에 알파카의 조상이 작성했던 문장이라 몇 글자가 지워져 있었다. 다행히 일부 남아있는 알파벳 글자들의 순서는 바뀌지 않아서 경현이가 고대 문장을 복원시켜 보려고 한다.

알파카들은 간결한 문장을 좋아하기 때문에 복원된 문장은 가능한 한 가장 짧아야 한다. 또, 방사성 추정에 의하여 이 문장은 서열이 K등인 알파카가 작성한 문장이기 때문에 가능한 최소 길이의 문장들 중에서 사전 순으로 K번째 문장을 찾아서 복원해야 한다.

경현이를 도와서 고대 알파카 문장을 복원하는 프로그램을 작성하시오.

#8651 upload 6 done 4 how_to_reg 3 call_split Subtask

알파카 문장 timer 3s memory 512MB

#8651
Subtask

알파카 문장 3s 512MB