Alpaca Sentence

A sentence written by an alpaca has the same letters read forwards and backwards. 'Do geese see god?' (dogeeseseegod), 'Amore, Roma.' and 'Rise to vote, sir.' are alpaca sentences.

Eungi was lying around the alpaca habitat reading alpaca novels. One day the alpacas were digging, and when he looked into the pit he found a stone slab with an ancient sentence written by an alpaca ancestor. Time erased a few letters, but the letters that survived kept their original order. Eungi wants to restore the sentence by inserting lowercase letters into the gaps.

The restored sentence must read the same forwards and backwards, and it must contain the surviving string $S$ as a subsequence.

Alpacas like short sentences, so the restored sentence has to be as short as possible. Radiometric dating also shows that an alpaca of rank $K$ wrote it, so among the sentences of minimum length you must choose the $K$-th one in lexicographic order.

Help Eungi and write a program that restores the ancient alpaca sentence.

The input consists of two lines.

The first line contains the surviving string $S$. $S$ consists of lowercase letters only, and its length is between $1$ and $2000$.

The second line contains the alpaca rank $K$, an integer with $1 \le K \le 10^{18}$.

Print the restored alpaca sentence on the first line.

If the number of sentences of minimum length is smaller than $K$, print NONE.