알파카 문장

알파카가 쓰는 문장은 앞에서 읽으나 뒤에서 읽으나 알파벳 배열이 같다. 'Do geese see god?'(dogeeseseegod), 'Amore, Roma.', 'Rise to vote, sir.'가 그런 문장이다.

은기는 알파카 서식지에서 알파카의 소설책을 읽으며 지내고 있었다. 어느 날 알파카들이 땅을 파길래 구덩이를 들여다보았더니 석판이 하나 있었고, 거기에 알파카의 조상이 남긴 고대 문장이 적혀 있었다. 오랜 세월에 몇 글자는 지워졌지만 남아 있는 글자의 순서는 그대로였다. 은기는 지워진 자리에 알파벳 소문자를 끼워 넣어 원래 문장을 복원하려고 한다.

즉 복원한 문장은 앞에서 읽으나 뒤에서 읽으나 같아야 하고, 남아 있는 문자열 $S$를 부분 수열로 포함해야 한다.

알파카는 간결한 문장을 좋아하므로 복원한 문장은 가능한 한 짧아야 한다. 또 방사성 연대 측정으로 이 문장을 서열 $K$등인 알파카가 썼다는 사실이 밝혀졌으므로, 최소 길이인 문장 중에서 사전 순으로 $K$번째인 것을 골라야 한다.

은기를 도와 고대 알파카 문장을 복원하는 프로그램을 작성하라.

입력은 두 줄로 이루어진다.

첫째 줄에 남아 있는 문자열 $S$가 주어진다. $S$는 알파벳 소문자로만 이루어지고, 길이는 $1$ 이상 $2000$ 이하이다.

둘째 줄에 알파카의 서열 $K$가 주어진다. $K$는 $1 \le K \le 10^{18}$을 만족하는 정수이다.

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

최소 길이인 문장의 개수가 $K$보다 적으면 NONE을 출력한다.