시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 27 6 6 23.077%

문제

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

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

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

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

은기를 도와서 고대 알파카 문장을 복원하는 프로그램을 작성해주세요!

입력

입력은 두 줄로 이루어집니다.

첫 번째 줄에는 유실된 알파카 문장 S이 주어집니다. S는 알파벳 소문자로만 이루어져 있고 S의 길이는 1 이상 2,000 이하입니다.

두 번째 줄에는 알파카의 서열 K가 주어집니다. K는 1 ≤ K ≤ 1018을 만족하는 정수입니다.

출력

첫 번째 줄에 복원한 알파카 문장을 출력합니다.

만약 최소 길이의 문장으로 가능한 경우의 수가 k보다 적다면, NONE을 출력합니다.

예제 입력

crc
1

예제 출력

crc

예제 입력 2

icpc
1

예제 출력 2

icpci

예제 입력 3

hello
1

예제 출력 3

heolloeh

예제 입력 4

hoge
8

예제 출력 4

hogegoh

예제 입력 5

hoge
9

예제 출력 5

NONE

예제 입력 6

bbaaab
2

예제 출력 6

NONE

예제 입력 7

thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500

예제 출력 7

feeberrthdstodxtksrnfacdjsohnlfuivdhqvqsozhgdqypllstwausnzcmjkboehgcerzvwxakyhswuojpfhzumvmlxxdfkmezmprlotpndbubbkblnjiedttmawsyqazekcftgshqbrhrtkzngaxbzfhnnlanxvphyfnkqmzcsdfscaawdleqaxtnhehwzgzwhehntxaqeldwaacsfdsczmqknfyhpvxnalnnhfzbxagnzktrhrbqhsgtfckezaqyswamttdeijnlbkbbubdnptolrpmzemkfdxxlmvmuzhfpjouwshykaxwvzrecgheobkjmcznsuawtsllpyqdghzosqvqhdviuflnhosjdcafnrsktxdotsdhtrrebeef

힌트