Problem Description

As is well-known, the red leaves of Fragrant Hill are quite famous. However, the CTSC is held in May, while the red leaves season is in autumn, so we cannot see the red leaves during this time. Therefore, during the CTSC competition, we can only discuss the trees of Fragrant Hill.

s-quark loves these trees and plans to attach a unique label to each tree. Each label is a strip that can be wrapped around the trunk. To distinguish each tree, s-quark prints a string of lowercase English letters on each label. Due to the circumference limitation of the trunk, the length of the string is also limited, thus the string can have at most \( N \) letters.

However, since the label is wrapped around the trunk, once attached to the tree, the starting position of the label cannot be identified anymore. Therefore, if two trees have labels that are cyclically isomorphic, such as "abc" and "cab", they cannot be distinguished by their labels. To address this issue, s-quark has devised a clever solution. For a label already attached to a tree, s-quark stipulates that the starting position must be the one that makes the string lexicographically smallest, i.e., if the string seen is "aba", then it can be inferred that the string seen from the correct starting position should be "aab".

Additionally, for some labels, such as "abab", although they comply with the lexicographically smallest rule, there are multiple such starting positions. s-quark considers this situation undesirable and thus avoids using such labels. s-quark has already numbered all the trees and plans to attach the label "a" to the first tree, and then attach different labels to each subsequent tree in lexicographical order.

For example, with \( n=3 \), s-quark will use these labels sequentially to mark the trees: \( a, aab, aac, \ldots, aaz, ab, abb, \ldots, abz, ac, \ldots \).

s-quark knows that there are a total of \( K \) trees on Fragrant Hill. He wants to know what label he will attach to the last tree. However, this problem is obviously too simple. Now, s-quark wants to ask you, if he attaches the label string \( S \) to the first tree, what label will he attach to the last tree?

Input Format

The first line contains two positive integers \( N \) and \( K \), representing the 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 Format

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 valid labels to cover all the trees.

Sample Input and Output

Sample Input #1

3 10
a

Sample Output #1

aaj

Sample Input #2

3 10
xy

Sample Output #2

yzz

Sample Input #3

1 100
a

Sample Output #3

-1

Sample Input #4

25 1000000000000000
u

Sample Output #4

uuuuuvxzuxvwwyzzuyzvxuvxw

Notes/Hints

For the first \( 10\% \) of the data, \( n = 8, K \leq 10^4, S = "a" \).

For another \( 10\% \) of the data, \( n = 9, K \leq 10^6 \).

For the remaining \( 70\% \) of the data:

• \( 30\% \) of the data have \( n \) values evenly distributed among \( 8, 9, 10 \).
• Another \( 20\% \) of the data have \( n \leq 30 \).

For \( 100\% \) of the data, \( n \leq 50, K \leq 10^{15} \).

见题面 Input 部分

见题面 Output 部分