{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given a string $$$s$$$ consisting of lowercase English letters and a number $$$k$$$. Let\u0027s call a string consisting of lowercase English letters \u003cspan class\u003d\"tex-font-style-it\"\u003ebeautiful\u003c/span\u003e if the number of occurrences of each letter in that string is divisible by $$$k$$$. You are asked to find the lexicographically smallest beautiful string of length $$$n$$$, which is lexicographically greater or equal to string $$$s$$$. If such a string does not exist, output $$$-1$$$.\u003c/p\u003e\u003cp\u003eA string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$a$$$ is a prefix of $$$b$$$, but $$$a \\ne b$$$; \u003c/li\u003e\u003cli\u003e in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$T$$$ ($$$1 \\le T \\le 10\\,000$$$) — the number of test cases.\u003c/p\u003e\u003cp\u003eThe next $$$2 \\cdot T$$$ lines contain the description of test cases. The description of each test case consists of two lines.\u003c/p\u003e\u003cp\u003eThe first line of the description contains two integers $$$n$$$ and $$$k$$$ ($$$1 \\le k \\le n \\le 10^5$$$) — the length of string $$$s$$$ and number $$$k$$$ respectively.\u003c/p\u003e\u003cp\u003eThe second line contains string $$$s$$$ consisting of lowercase English letters.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case output in a separate line lexicographically smallest beautiful string of length $$$n$$$, which is greater or equal to string $$$s$$$, or $$$-1$$$ if such a string does not exist.\u003c/p\u003e"}},{"title":"Examples","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\u003e4\n4 2\nabcd\n3 1\nabc\n4 3\naaaa\n9 3\nabaabaaaa\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eacac\nabc\n-1\nabaabaaab\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eacac\u003c/span\u003e\" is greater than or equal to $$$s$$$, and each letter appears $$$2$$$ or $$$0$$$ times in it, so it is beautiful.\u003c/p\u003e\u003cp\u003eIn the second test case each letter appears $$$0$$$ or $$$1$$$ times in $$$s$$$, so $$$s$$$ itself is the answer.\u003c/p\u003e\u003cp\u003eWe can show that there is no suitable string in the third test case.\u003c/p\u003e\u003cp\u003eIn the fourth test case each letter appears $$$0$$$, $$$3$$$, or $$$6$$$ times in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eabaabaaab\u003c/span\u003e\". All these integers are divisible by $$$3$$$.\u003c/p\u003e"}}]}