Шифр
Шпигун використовує хитромудрий метод шифрування для кодування та декодування повідомлень. Цей метод надзвичайно ефективний, оскільки дозволяє йому надсилати та отримувати будь-яке повідомлення, незалежно від його довжини, використовуючи лише три числа!
Після численних зусиль Департамент національної безпеки зміг розгадати, як працює цей метод:
По-перше, використовуються лише пробіл і малі англійські літери. Кожному символу присвоєно ціле число, яке називається обсягом символу: пробіл має обсяг 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, тому щось пішло не так!