This challenge uses the famous KMP algorithm. It isn't really important to understand how KMP works, but you should understand what it calculates.

A KMP algorithm takes a string, , of length as input. Let's assume that the characters in are indexed from to ; for every prefix of , the algorithm calculates the length of its longest valid border in linear complexity. In other words, for every (where ) it calculates the largest (where ) such that for every (where ) there is .

Here is an implementation example of KMP:

kmp[1] = 0;
for (i = 2; i <= N; i = i + 1){
    l = kmp[i - 1];
    while (l > 0 && S[i] != S[l + 1]){
        l = kmp[l];
    }
    if (S[i] == S[l + 1]){
        kmp[i] = l + 1;
    }
    else{
        kmp[i] = 0;
    }
}

Given a sequence , construct a string, , that meets the following conditions:

1. The frequency of letter '' in is exactly , the frequency of letter '' in is exactly , and so on.
2. Let's assume characters of are numbered from to , where . We apply the KMP algorithm to and get a table, , of size . You must ensure that the sum of for all is minimal.

If there are multiple strings which fulfill the above conditions, print the lexicographically smallest one.