400400: GYM100162 G Lyndon Words

Lyndon word is a string that is strictly smaller in lexicographic order than all of its cyclic shifts. For example, "abbac" is a Lyndon word, but "abbab" is not.

You are given two positive integers n and m. Consider all Lyndon words not longer than n characters and containing letters from the first m letters of English alphabet. Let's numerate them in lexicographic order starting from 1. Write a program which will display the part of this list from the number l to the number r inclusively.

The input contains several test cases. Each test case contains four positive integers n, m, l and r (1 ≤ n ≤ 30; 2 ≤ m ≤ 26; 1 ≤ l ≤ r ≤ 10⁷). It is guaranteed that r - l < 10⁵ and there are at least r Lyndon words not longer than n containing letters from the first m letters of English alphabet.

Display the test case number and the required list of words, one word per line. Order words lexicographically.

4 3 7 12
4 3 31 32

Case 1:
aac
aacb
aacc
ab
abac
abb
Case 2:
bccc
c

There are 32 Lyndon words for n = 4 and m = 3: a, aaab, aaac, aab, aabb, aabc, aac, aacb, aacc, ab, abac, abb, abbb, abbc, abc, abcb, abcc, ac, acb, acbb, acbc, acc, accb, accc, b, bbbc, bbc, bbcc, bc, bcc, bccc, c.