Словом Линдона называется строка, которая строго меньше в лексикографическом порядке, чем все ее циклические сдвиги. К примеру, «abbac» — это слово Линдона, а «abbab» — нет.
Вам заданы два положительных целых числа n и m. Рассмотрим все слова Линдона длиной не более n символов над алфавитом из первых m букв латинского алфавита. Пронумеруем эти слова в лексикографическом порядке, начиная с единицы. Напишите программу, которая выводит часть этого отсортированного списка с позиции l по позицию r включительно.
Входные данные состоят из нескольких тестовых наборов. Каждый тестовый набор содержит четыре целых числа n, m, l и r (1 ≤ n ≤ 30; 2 ≤ m ≤ 26; 1 ≤ l ≤ r ≤ 107). Гарантируется, что r - l < 105, и существует не менее r слов Линдона длины не более n, составленных из m первых символов латинского алфавита.
Для каждого тестового набора выведите его порядковый номер и искомый список слов, по одному в строке. При выводе упорядочивайте слова лексикографически.
4 3 7 12
4 3 31 32
Case 1:
aac
aacb
aacc
ab
abac
abb
Case 2:
bccc
c
Имеется 32 слова Линдона для n = 4 и 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.
