Description

As everyone knows, Xiangshan is famous for its red leaves. However, CTSC is held in May, while the season for red leaves is autumn, so you cannot see red leaves at this time. Therefore, in the CTSC contest we can only talk about the trees of Xiangshan.

s-quark likes these trees very much, and he plans to put a distinct label on each tree. Each label is a strip that can be wrapped around the trunk into a circle. To tell every tree apart, s-quark prints on each label a string made of lowercase English letters. Due to the limit of the trunk circumference, the label length is also limited, so the string can contain at most $N$ letters.

However, since the label is wrapped into a circle around the trunk, after the label is attached, you can no longer find the starting position of the label. So, if the labels on two trees are cyclically isomorphic, for example "abc" and "cab", then these two trees can no longer be distinguished by their labels. To solve this, s-quark came up with a clever method. For a label that has already been attached to a tree, s-quark requires that its starting position must be the one that makes the string lexicographically smallest. That is, if the string you see is "aba", then you can infer that the string starting from the correct position should be "aab".

In addition, for some labels such as "abab", although they satisfy the lexicographically smallest rule, such a starting position is not unique, and s-quark thinks this is also undesirable. Therefore, s-quark will also avoid using such labels. s-quark has already ordered all the trees and plans to put the label "a" on the first tree, and then attach different labels to each tree in lexicographical order.

Take $n = 3$ as an example, s-quark will use the following labels in order to mark these trees: $a ,~aab ,~ aac , ~\dots~, ~ aaz , ~ab , ~ abb , ~\dots~, ~ abz , ~ ac , \dots~$.

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

Input Format

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

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 only one line. Output a string $T$, representing the label that s-quark will attach to the last tree, or output $-1$ to indicate that the number of remaining valid labels is not enough to label all trees.

3 10
a

aaj

3 10
xy

yzz

1 100
a

-1

25 1000000000000000
u

uuuuuvxzuxvwwyzzuyzvxuvxw

Hint

For the first $10\%$ of the testdata, $n = 8,~K~\leq~10^4,~S = "a"$.

Another $10\%$ of the testdata has $n = 9,~K~\leq~10^6$.

For the remaining $70\%$ of the testdata:

$30\%$ of the testdata has $n$ equal to $8,~9~10$, uniformly distributed within this $30\%$ of the testdata.

Another $20\%$ of the testdata has $n~\leq~30$.

For $100\%$ of the testdata, $n~\leq~50,~K~\leq~10^{15}$.

Translated by ChatGPT 5