{"trustable":false,"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\u003e给定一个由小写英文字母组成的字符串 $$$s$$$,以及一个整数 $$$k$$$。\u003c/p\u003e\n\n\u003cp\u003e如果字符串中每个字母的出现次数都能被 $$$k$$$ 整除,则称该字符串为 \u003cstrong\u003e美丽的\u003c/strong\u003e。请找出长度为 $$$n$$$ 的美丽字符串,其字典序最小,且字典序大于或等于字符串 $$$s$$$。如果不存在这样的字符串,则输出 $$$-1$$$。\u003c/p\u003e\n\n\u003cp\u003e字符串 $$$a$$$ 的字典序小于字符串 $$$b$$$,当且仅当以下情况之一成立:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e$$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \\ne b$$$;\u003c/li\u003e\n\u003cli\u003e在 $$$a$$$ 和 $$$b$$$ 出现不同字符的首个位置,字符串 $$$a$$$ 的字母在字母表中的顺序早于 $$$b$$$ 对应位置的字母。\u003c/li\u003e\n\u003c/ul\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$T$$$ $$$(1 \\le T \\le 10^4)$$$,表示测试用例的数量。\u003c/p\u003e\n\n\u003cp\u003e接下来的 $$$2T$$$ 行包含测试用例的描述。每个测试用例由两行组成。\u003c/p\u003e\n\n\u003cp\u003e测试用例的第一行包含两个整数 $$$n,k$$$ $$$(1 \\leq k \\leq n \\leq 10^5)$$$,分别表示字符串 $$$s$$$ 的长度,以及整数 $$$k$$$。\u003c/p\u003e\n\n\u003cp\u003e测试用例的第二行包含一个字符串 $$$s$$$,由小写英文字母组成。\u003c/p\u003e\n\n\u003cp\u003e保证所有测试用例中,$$$n$$$ 的总和不超过 $$$10^5$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,在单独一行中输出长度为 $$$n$$$、字典序最小、且字典序大于或等于字符串 $$$s$$$ 的美丽字符串。\u003c/p\u003e\n\n\u003cp\u003e如果不存在这样的字符串,则输出 $$$-1$$$。\u003c/p\u003e"}},{"title":"示例 1","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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试用例中,\"acac\" 大于或等于 $$$s$$$,且每个字母在其中出现 $$$2$$$ 或 $$$0$$$ 次,因此是美丽的。\u003c/p\u003e\n\n\u003cp\u003e在第二个测试用例中,每个字母在 $$$s$$$ 中出现 $$$0$$$ 或 $$$1$$$ 次,因此答案为 $$$s$$$ 本身。\u003c/p\u003e\n\n\u003cp\u003e可以证明,第三个测试用例中没有合适的字符串。\u003c/p\u003e\n\n\u003cp\u003e在第四个测试用例中,\"abaabaaab\" 中每个字母出现 $$$0$$$、$$$3$$$ 或 $$$6$$$ 次。所有这些整数都能被 $$$3$$$ 整除。\u003c/p\u003e"}}]}