Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. K-beautiful Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string $$$s$$$ consisting of lowercase English letters and a number $$$k$$$. Let's call a string consisting of lowercase English letters beautiful 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$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- 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$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.

The next $$$2 \cdot T$$$ lines contain the description of test cases. The description of each test case consists of two lines.

The 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.

The second line contains string $$$s$$$ consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For 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.

Example

Input

4 4 2 abcd 3 1 abc 4 3 aaaa 9 3 abaabaaaa

Output

acac abc -1 abaabaaab

Note

In the first test case "acac" is greater than or equal to $$$s$$$, and each letter appears $$$2$$$ or $$$0$$$ times in it, so it is beautiful.

In the second test case each letter appears $$$0$$$ or $$$1$$$ times in $$$s$$$, so $$$s$$$ itself is the answer.

We can show that there is no suitable string in the third test case.

In the fourth test case each letter appears $$$0$$$, $$$3$$$, or $$$6$$$ times in "abaabaaab". All these integers are divisible by $$$3$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/27/2023 20:28:32 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|