문제
알파카는 언제나 신비롭다. 알파카들이 사용하는 문장들도 매우 신비한데, 알파카들의 문장에서 등장하는 알파벳들은 앞에서부터 읽으나 뒤에서부터 읽으나 항상 똑같다. 알파카 문장의 예로는 'Do geese see god?' (dogeeseseegod), 'Amore, Roma.', 'Rise to vote, sir.' 등이 있다.
경현이는 알파카를 매우 좋아하기 때문에 알파카들의 서식지에서 빈둥빈둥대면서 알파카들의 소설책을 읽고 있었다.
그러던 어느 날, 알파카들이 땅을 파고 있었다. 궁금한 경현이가 구덩이를 보았더니 석판에 고대 알파카 문장이 적혀있었다. 이 문장은 약 46억 년 전에 알파카의 조상이 작성했던 문장이라 몇 글자가 지워져 있었다. 다행히 일부 남아있는 알파벳 글자들의 순서는 바뀌지 않아서 경현이가 고대 문장을 복원시켜 보려고 한다.
알파카들은 간결한 문장을 좋아하기 때문에 복원된 문장은 가능한 한 가장 짧아야 한다. 또, 방사성 추정에 의하여 이 문장은 서열이
경현이를 도와서 고대 알파카 문장을 복원하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 유실된 알파카 문장
S 는 알파벳 소문자로만 이루어져 있고S 의 길이를 의미하는|S| 는1 이상2\,000 이하다.
두 번째 줄에는 알파카의 서열
K 는1 ≤ K ≤ 10^{18} 을 만족하는 정수다.
출력
첫 번째 줄에 복원한 알파카 문장을 출력한다.
만약 최소 길이의 문장으로 가능한 경우의 수가
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 20점 | |
| #3 | 30점 | |
| #4 | 40점 | 추가 제약 조건 없음 |
예제 #1
crc
1
crc
예제 #2
icpc
1
icpci
예제 #3
hello
1
heolloeh
예제 #4
hoge
8
hogegoh
예제 #5
hoge
9
NONE
예제 #6
bbaaab
2
NONE
예제 #7
thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500
feeberrthdstodxtksrnfacdjsohnlfuivdhqvqsozhgdqypllstwausnzcmjkboehgcerzvwxakyhswuojpfhzumvmlxxdfkmezmprlotpndbubbkblnjiedttmawsyqazekcftgshqbrhrtkzngaxbzfhnnlanxvphyfnkqmzcsdfscaawdleqaxtnhehwzgzwhehntxaqeldwaacsfdsczmqknfyhpvxnalnnhfzbxagnzktrhrbqhsgtfckezaqyswamttdeijnlbkbbubdnptolrpmzemkfdxxlmvmuzhfpjouwshykaxwvzrecgheobkjmcznsuawtsllpyqdghzosqvqhdviuflnhosjdcafnrsktxdotsdhtrrebeef
로그인해야 코드를 작성할 수 있어요.