回文是指一个正读和反读都相同的字符序列。著名的例子包括 “dogeeseseegod”（“Do geese see God?”）、“amoreroma”（“Amore, Roma.”）和 “risetovotesir”（“Rise to vote, sir.”）。

在筑波山脚下的一座寺庙里，流传着一部古老的经文。据说这部经文原本是一个回文，但在传抄过程中丢失了一些字符。

一位著名的宗教学者受邀负责恢复原稿。经过长时间反复推敲，他得出结论：恢复原稿的信息并未丢失，原稿可以被重构为包含当前经文所有字符且保持原有顺序的最短回文。也就是说，原稿是通过在当前经文的字符之前、之间和/或之后添加一些字符而得到的。

给定一个字符序列，你的程序应该输出包含当前经文字符且保持其顺序的最短回文之一。是“其中之一”吗？是的，可能存在多个最短回文。题目要求输出其中按字典序排列的第 $k$ 个。

例如，如果当前的经文是 cdba 且指定为第 7 个，你的程序应该在 8 个候选者 abcdcba、abdcdba、acbdbca、acdbdca、cabdbac、cadbdac、cdabadc 和 cdbabdc 中输出 cdabadc。

输入格式

输入包含一组测试数据。测试数据格式如下：

$S$ $k$

第一行包含一个由小写字母 ‘a’ 到 ‘z’ 组成的字符串 $S$。$S$ 的长度大于 0 且小于等于 2000。第二行包含一个整数 $k$，表示在所有候选原稿中按字典序排列的排名。 $1 \le k \le 10^{18}$。

输出格式

输出所有候选原稿中按字典序排列的第 $k$ 个字符串。如果候选者的数量少于 $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

thdstodxtksrnfacdsohnlfuivqvqsozdstwa
szmkboehgcerwxawuojpfuvlxxdfkezprodne
ttawsyqazekcftgqbrrtkzngaxzlnphynkmsd
sdleqaxnhehwzgzwtldwaacfczqkfpvxnalnn
hfzbagzhqhstcymdeijlbkbbubdnptolrmemf
xlmmzhfpshykxvzbjmcnsusllpyqghzhdvljd
xrrebeef
11469362357953500

样例输出 7

feeberrthdstodxtksrnfacdjsohnlfuivdhq
vqsozhgdqypllstwausnzcmjkboehgcerzvwx
akyhswuojpfhzumvmlxxdfkmezmprlotpndbu
bbkblnjiedttmawsyqazekcftgshqbrhrtkzn
gaxbzfhnnlanxvphyfnkqmzcsdfscaawdleqa
xtnhehwzgzwhehntxaqeldwaacsfdsczmqknf
yhpvxnalnnhfzbxagnzktrhrbqhsgtfckezaq
yswamttdeijnlbkbbubdnptolrpmzemkfdxxl
mvmuzhfpjouwshykaxwvzrecgheobkjmcznsu
awtsllpyqdghzosqvqhdviuflnhosjdcafnrs
ktxdotsdhtrrebeef