시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 54 24 23 45.098%

문제

알파카는 언제나 신비롭습니다. 알파카들이 사용하는 문장들도 매우 신비한데, 알파카들의 문장에서 등장하는 알파벳들은 앞에서부터 읽으나 뒤에서부터 읽으나 항상 똑같습니다. 알파카 문장의 예로는 '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을 출력합니다.

예제 입력 1

crc
1

예제 출력 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
W3sicHJvYmxlbV9pZCI6IjExNzUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTRjXHVkMzBjXHVjZTc0IFx1YmIzOFx1YzdhNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTRjXHVkMzBjXHVjZTc0XHViMjk0IFx1YzViOFx1YzgxY1x1YjA5OCBcdWMyZTBcdWJlNDRcdWI4NmRcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc3NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHViYjM4XHVjN2E1XHViNGU0XHViM2M0IFx1YjllNFx1YzZiMCBcdWMyZTBcdWJlNDRcdWQ1NWNcdWIzNzAsIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc1OCBcdWJiMzhcdWM3YTVcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YjRlNFx1Yzc0MCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNzdkXHVjNzNjXHViMDk4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM3N2RcdWM3M2NcdWIwOTggXHVkNTZkXHVjMGMxIFx1YjYxMVx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNTRjXHVkMzBjXHVjZTc0IFx1YmIzOFx1YzdhNVx1Yzc1OCBcdWM2MDhcdWI4NWNcdWIyOTQgJiMzOTtEbyBnZWVzZSBzZWUgZ29kPyYjMzk7IChkb2dlZXNlc2VlZ29kKSwgJiMzOTtBbW9yZSwgUm9tYS4mIzM5OywgJiMzOTtSaXNlIHRvIHZvdGUsIHNpci4mIzM5OyBcdWI0ZjFcdWM3NzQgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWIyOTQgXHVjNTRjXHVkMzBjXHVjZTc0XHViOTdjIFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc1OCBcdWMxMWNcdWMyZGRcdWM5YzBcdWM1ZDBcdWMxMWMgXHViZTQ4XHViNDY1XHViZTQ4XHViNDY1XHViMzAwXHViYTc0XHVjMTFjIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc1OCBcdWMxOGNcdWMxMjRcdWNjNDVcdWM3NDQgXHVjNzdkXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMzU4IFx1YzViNFx1YjI5MCBcdWIwYTAsIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc3NCBcdWM3NzRcdWMwYzFcdWQ1NWNcdWM5YzAgXHViNTQ1XHVjNzQ0IFx1ZDMwY1x1YWNlMCBcdWM3ODhcdWM1YzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YWQ4MVx1YWUwOFx1ZDU1YyBcdWM3NDBcdWFlMzBcdWFjMDAgXHVhZDZjXHViMzY5XHVjNzc0XHViOTdjIFx1YmNmNFx1YzU1OFx1YjM1NFx1YjJjOCBcdWMxMWRcdWQzMTBcdWM1ZDAgXHVhY2UwXHViMzAwIFx1YzU0Y1x1ZDMwY1x1Y2U3NCBcdWJiMzhcdWM3YTVcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHVjNWM4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjN2E1XHVjNzQwIFx1YzU3ZCA0Nlx1YzViNSBcdWIxNDQgXHVjODA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1Y2U3NFx1Yzc1OCBcdWM4NzBcdWMwYzFcdWM3NzQgXHVjNzkxXHVjMTMxXHVkNTg4XHViMzU4IFx1YmIzOFx1YzdhNVx1Yzc3NFx1Yjc3YyBcdWJhODcgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzljMFx1YzZjY1x1YzgzOCBcdWM3ODhcdWM1YzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjJlNFx1ZDU4OVx1ZDc4OCBcdWM3N2NcdWJkODAgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YmMxNFx1YjAwY1x1YzljMCBcdWM1NGFcdWM1NDRcdWMxMWMgXHVjNzQwXHVhZTMwXHVhYzAwIFx1YWNlMFx1YjMwMCBcdWJiMzhcdWM3YTVcdWM3NDQgXHViY2Y1XHVjNmQwXHVjMmRjXHVjZjFjIFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1ZDMwY1x1Y2U3NFx1YjRlNFx1Yzc0MCBcdWFjMDRcdWFjYjBcdWQ1NWMgXHViYjM4XHVjN2E1XHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViY2Y1XHVjNmQwXHViNDFjIFx1YmIzOFx1YzdhNVx1Yzc0MCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM1NDRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LiBcdWI2MTAsIFx1YmMyOVx1YzBhY1x1YzEzMSBcdWNkOTRcdWM4MTVcdWM1ZDAgXHVjNzU4XHVkNTU4XHVjNWVjIFx1Yzc3NCBcdWJiMzhcdWM3YTVcdWM3NDAgXHVjMTFjXHVjNWY0XHVjNzc0IEtcdWI0ZjFcdWM3NzggXHVjNTRjXHVkMzBjXHVjZTc0XHVhYzAwIFx1Yzc5MVx1YzEzMVx1ZDU1YyBcdWJiMzhcdWM3YTVcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YmIzOFx1YzdhNVx1YjRlNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBLXHViYzg4XHVjOWY4IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWNjM2VcdWM1NDRcdWMxMWMgXHViY2Y1XHVjNmQwXHVkNTc0XHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzQwXHVhZTMwXHViOTdjIFx1YjNjNFx1YzY0MFx1YzExYyBcdWFjZTBcdWIzMDAgXHVjNTRjXHVkMzBjXHVjZTc0IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWJjZjVcdWM2ZDBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YzhmY1x1YzEzOFx1YzY5NCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzIwXHVjMmU0XHViNDFjIFx1YzU0Y1x1ZDMwY1x1Y2U3NCBcdWJiMzhcdWM3YTUgU1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFNcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwIFNcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEgXHVjNzc0XHVjMGMxIDIsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHVjZTc0XHVjNzU4IFx1YzExY1x1YzVmNCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gS1x1YjI5NCAxICZsZTsgSyAmbGU7IDEwPHN1cD4xODxcL3N1cD5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjZjVcdWM2ZDBcdWQ1NWMgXHVjNTRjXHVkMzBjXHVjZTc0IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCZuYnNwO1x1Y2Q1Y1x1YzE4YyBcdWFlMzhcdWM3NzRcdWM3NTggXHViYjM4XHVjN2E1XHVjNzNjXHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHVhYzAwIGtcdWJjZjRcdWIyZTQgXHVjODAxXHViMmU0XHViYTc0LCBOT05FXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTc1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRvIEdlZXNlIFNlZSBHb2Q/IiwiZGVzY3JpcHRpb24iOiI8cD5BIHBhbGluZHJvbWUgaXMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIHdoaWNoIHJlYWRzIHRoZSBzYW1lIGJhY2t3YXJkIG9yIGZvcndhcmQuIEZhbW91cyBvbmVzIGluY2x1ZGUgJmxkcXVvO2RvZ2Vlc2VzZWVnb2QmcmRxdW87ICgmbGRxdW87RG8gZ2Vlc2Ugc2VlIEdvZD8mcmRxdW87KSwgJmxkcXVvO2Ftb3Jlcm9tYSZyZHF1bzsgKCZsZHF1bztBbW9yZSwgUm9tYS4mcmRxdW87KSBhbmQgJmxkcXVvO3Jpc2V0b3ZvdGVzaXImcmRxdW87ICgmbGRxdW87UmlzZSB0byB2b3RlLCBzaXIuJnJkcXVvOykuPFwvcD5cclxuXHJcbjxwPkFuIGFuY2llbnQgc3V0cmEgaGFzIGJlZW4gaGFuZGVkIGRvd24gdGhyb3VnaCBnZW5lcmF0aW9ucyBhdCBhIHRlbXBsZSBvbiBUc3VrdWJhIGZvb3RoaWxscy4gVGhleSBzYXkgdGhlIHN1dHJhIHdhcyBhIHBhbGluZHJvbWUsIGJ1dCBzb21lIG9mIHRoZSBjaGFyYWN0ZXJzIGhhdmUgYmVlbiBkcm9wcGVkIHRocm91Z2ggdHJhbnNjcmlwdGlvbi48XC9wPlxyXG5cclxuPHA+QSBmYW1vdXMgc2Nob2xhciBpbiB0aGUgZmllbGQgb2YgcmVsaWdpb3VzIHN0dWRpZXMgd2FzIGFza2VkIHRvIHJlY292ZXIgdGhlIG9yaWdpbmFsLiBBZnRlciBsb25nIHJlcGVhdGVkIGRlbGliZXJhdGlvbnMsIGhlIGNvbmNsdWRlZCB0aGF0IG5vIGluZm9ybWF0aW9uIHRvIHJlY292ZXIgdGhlIG9yaWdpbmFsIGhhcyBiZWVuIGxvc3QsIGFuZCB0aGF0IHRoZSBvcmlnaW5hbCBjYW4gYmUgcmVjb25zdHJ1Y3RlZCBhcyB0aGUgc2hvcnRlc3QgcGFsaW5kcm9tZSBpbmNsdWRpbmcgYWxsIHRoZSBjaGFyYWN0ZXJzIG9mIHRoZSBjdXJyZW50IHN1dHJhIGluIHRoZSBzYW1lIG9yZGVyLiBUaGF0IGlzIHRvIHNheSwgdGhlIG9yaWdpbmFsIHN1dHJhIGlzIG9idGFpbmVkIGJ5IGFkZGluZyBzb21lIGNoYXJhY3RlcnMgYmVmb3JlLCBiZXR3ZWVuLCBhbmRcL29yIGJlaGluZCB0aGUgY2hhcmFjdGVycyBvZiB0aGUgY3VycmVudC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBjaGFyYWN0ZXIgc2VxdWVuY2UsIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IG9uZSBvZiB0aGUgc2hvcnRlc3QgcGFsaW5kcm9tZXMgY29udGFpbmluZyB0aGUgY2hhcmFjdGVycyBvZiB0aGUgY3VycmVudCBzdXRyYSBwcmVzZXJ2aW5nIHRoZWlyIG9yZGVyLiBPbmUgb2YgdGhlIHNob3J0ZXN0PyBZZXMsIG1vcmUgdGhhbiBvbmUgc2hvcnRlc3QgcGFsaW5kcm9tZXMgbWF5IGV4aXN0LiBXaGljaCBvZiB0aGVtIHRvIG91dHB1dCBpcyBhbHNvIHNwZWNpZmllZCBhcyBpdHMgcmFuayBhbW9uZyB0aGUgY2FuZGlkYXRlcyBpbiB0aGUgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGN1cnJlbnQgc3V0cmEgaXMgY2RiYSBhbmQgN3RoIGlzIHNwZWNpZmllZCwgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgY2RhYmFkYyBhbW9uZyB0aGUgOCBjYW5kaWRhdGVzLCBhYmNkY2JhLCBhYmRjZGJhLCBhY2JkYmNhLCBhY2RiZGNhLCBjYWJkYmFjLCBjYWRiZGFjLCBjZGFiYWRjIGFuZCBjZGJhYmRjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIHRlc3QgY2FzZS4gVGhlIHRlc3QgY2FzZSBpcyBmb3JtYXR0ZWQgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHByZT5cclxuU1xyXG5rPFwvcHJlPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYSBzdHJpbmcgUyBjb21wb3NlZCBvZiBsb3dlcmNhc2UgbGV0dGVycyBmcm9tICZsc3F1bzthJnJzcXVvOyB0byAmbHNxdW87eiZyc3F1bzsuIFRoZSBsZW5ndGggb2YgUyBpcyBncmVhdGVyIHRoYW4gMCwgYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byAyMDAwLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBrIHdoaWNoIHJlcHJlc2VudHMgdGhlIHJhbmsgaW4gdGhlIGxleGljb2dyYXBoaWNhbCBvcmRlciBhbW9uZyB0aGUgY2FuZGlkYXRlcyBvZiB0aGUgb3JpZ2luYWwgc3V0cmEuIDEgJmxlOyBrICZsZTsgMTA8c3VwPjE4PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGstdGggc3RyaW5nIGluIHRoZSBsZXhpY29ncmFwaGljYWwgb3JkZXIgYW1vbmcgdGhlIGNhbmRpZGF0ZXMgb2YgdGhlIG9yaWdpbmFsIHN1dHJhLiBJZiB0aGUgbnVtYmVyIG9mIHRoZSBjYW5kaWRhdGVzIGlzIGxlc3MgdGhhbiBrLCBvdXRwdXQgTk9ORS48XC9wPlxyXG5cclxuPHA+VGhvdWdoIHRoZSBmaXJzdCBsaW5lcyBvZiB0aGUgU2FtcGxlIElucHV0XC9PdXRwdXQgNyBhcmUgZm9sZGVkIGF0IHRoZSByaWdodCBtYXJnaW4sIHRoZXkgYXJlIGFjdHVhbGx5IHNpbmdsZSBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=