Шифр
Шпион использует хитроумную технику шифрования для кодирования и декодирования сообщений. Эта техника очень эффективна, так как позволяет ему отправлять и получать любое сообщение, независимо от его длины, используя всего три числа!
После многих усилий Департамент национальной безопасности смог выяснить, как работает эта техника:
Используются только пробел и строчные английские буквы. Каждому символу присваивается целое число, называемое объемом символа: пробел имеет объем 1, 'a' имеет объем 2, 'b' имеет объем 3 и так далее до 'z', который имеет объем 27. Объем всего сообщения V — это сумма объемов символов в сообщении.
Сообщение состоит из нескольких слов W, слово — это последовательность строчных букв. Сообщения не имеют начальных или конечных пробелов, и между последовательными словами есть только один пробел.
Для заданных V и W, пусть S будет лексикографически отсортированным множеством сообщений, имеющих объем V и состоящих ровно из W слов. Мы можем ссылаться на определенное сообщение, используя его индекс I в S, начиная с единицы.
Таким образом, когда шпион хочет отправить сообщение M, он вычисляет его объем V и количество слов W, находит его индекс I в соответствующем множестве S (его индекс среди всех отсортированных сообщений объема V с W словами) и отправляет только три числа: V, W и I!
Департамент национальной безопасности проделал большую работу, но теперь они нуждаются в вашей помощи для декодирования сообщений, отправленных шпионом! То есть, имея V, W и I, вы должны расшифровать сообщение шпиона или определить, что такого сообщения не существует!
Входные данные
Первая строка ввода содержит целое число (1 ≤ T ≤ 200), количество тестовых случаев. Каждый набор данных состоит из строки с тремя целыми числами: объем сообщения (1 ≤ V ≤ 75), количество слов (1 ≤ W ≤ 20) и индекс сообщения (1 ≤ I ≤ 10^18).
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую расшифрованное сообщение, или "Corrupted!", если не существует допустимого сообщения, соответствующего данным входным данным.
Подсказка
В первом тестовом случае отсортированное множество сообщений объема 7, содержащих 2 слова, это {"a aa", "a c", "aa a", "b b", "c a"}, следовательно, третье и требуемое сообщение — “aa a”. Во втором тестовом случае отсортированное множество сообщений объема 2, содержащих 1 слово, это {"a"}, множество содержит только одно сообщение, в то время как требуется индекс 2, так что что-то должно было пойти не так!