{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Long long ago, there lived a lot of rabbits in the forest. One day, the king of the rabbit kingdom got a mysterious string and he wanted to study this string.\u003cbr\u003e\u003cbr\u003e At first, he would divide this string into no more than k substrings. Then for each substring S, he looked at all substrings of S, and selected the one which has the largest dictionary order. Among those substrings selected in the second round, the king then choose one which has the largest dictionary order, and name it as a \"magic string\".\u003cbr\u003e\u003cbr\u003e Now he wanted to figure out how to divide the string so that the dictionary order of that \"magic string\" is as small as possible.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are at most 36 test cases.\u003cbr\u003e\u003cbr\u003e For each test case, the first line contains a integer k indicating the maximum number of substrings the king could divide, and the second line is the original mysterious string which consisted of only lower letters.\u003cbr\u003e\u003cbr\u003e The length of the mysterious string is between 1 and 10\u003csup\u003e5\u003c/sup\u003e and k is between 1 and the length of the mysterious string, inclusive.\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003cbr\u003e The input ends by k \u003d 0."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, output the magic string."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\nbbaa\r\n2\r\nababa\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eb\r\nba\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":" For the first test case, the king may divide the string into \"b\", \"b\" and \"aa\".\u003cbr\u003e For the second test case, the king may divide the string into \"aba\" and \"ba\"."}}]}