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