As everyone knows, the red leaves of Xiangshan are very famous. However, CTSC is held in May, while the red leaf season is in autumn, so one cannot see red leaves during this season. Therefore, we can only discuss the trees of Xiangshan during the CTSC competition.

s-quark likes these trees very much and plans to attach a unique label to each tree. Each label is strip-shaped and can be wrapped around the trunk in a circle. To distinguish each tree, s-quark has printed a string consisting of lowercase English letters on each label. Due to the limitation of the trunk's circumference, the length of the label is also limited, so this string can consist of at most $N$ letters.

However, since the label is wrapped in a circle on the trunk, the starting position of the label cannot be found once it is attached to the tree. Therefore, if the labels on two trees are cyclically isomorphic, for example, "abc" and "cab", then these two trees cannot be distinguished by their labels. To solve this problem, s-quark came up with a clever method. For a label already attached to a tree, s-quark stipulates that its starting position must be the one that makes the lexicographical order of the string minimal. That is, if the observed string is "aba", one can infer that the string starting from the correct starting position should be "aab".

In addition, for some labels, such as "abab", although they meet the rule of minimal lexicographical order, such a starting position is not unique. s-quark believes that this situation is also undesirable. Therefore, s-quark will also avoid using such labels. s-quark has already numbered all the trees and is prepared to attach the label "a" to the first tree, and then attach different labels to each tree in lexicographical order.

Taking $n=3$ as an example, s-quark will use these labels to mark the trees in order: a, aab, aac, …, aaz, ab, abb, …, abz, ac, …

s-quark knows that there are a total of $K$ trees on Xiangshan. He wants to know what the label on the last tree will be. However, this problem is obviously too simple. Now, s-quark asks you: if the label he attaches to the first tree is the string $S$, what will be the label he attaches to the last tree?

Input

The first line contains two positive integers $N$ and $K$, representing the maximum length of the string and the total number of trees, respectively.

The second line contains a string $S$ consisting of lowercase English letters, representing the label attached to the first tree. The length of $S$ does not exceed $N$, and it is guaranteed to be a valid label.

Output

Output a single line containing a string $T$, representing the label s-quark will attach to the last tree, or output $-1$ if there are not enough remaining valid labels to cover all the trees.

Examples

Input 1

3 10
a

Output 1

aaj

Input 2

3 10
xy

Output 2

yzz

Input 3

1 100
a

Output 3

-1

Input 4

25 1000000000000000
u

Output 4

uuuuuvxzuxvwwyzzuyzvxuvxw

Subtasks