Шифр#2728

Шифр

1 секунда

64 мегабайти

Складна

Шпигун використовує хитру техніку шифрування для кодування та декодування повідомлень. Ця техніка дуже ефективна, оскільки дозволяє йому надсилати й отримувати будь-яке повідомлення, незалежно від його довжини, використовуючи лише три числа!

Після багатьох зусиль Департамент національної безпеки зумів розгадати, як працює ця техніка:

Насамперед, використовуються лише пробіл та малі англійські літери. Кожному символу надається ціле число, яке називається об'ємом символу: пробіл має об'єм $1$ , 'a' має об'єм $2$ , 'b' має об'єм $3$ і так далі, аж до 'z', яка має об'єм $27$ . Об'єм усього повідомлення $V$ — це сума об'ємів символів у повідомленні.
Повідомлення складається з певної кількості слів $W$ . Слово — це послідовність підряд ідучих малих літер; у повідомленнях немає початкових або кінцевих пробілів, і між сусідніми словами є лише один пробіл.
Для певних $V$ та $W$ нехай $S$ — це лексикографічно впорядкована множина повідомлень, які мають об'єм $V$ та складаються рівно з $W$ слів. Ми можемо посилатися на певне повідомлення, використовуючи його порядковий номер $I$ (нумерується з 1) у $S$ .

Отже, коли шпигун хоче надіслати повідомлення $M$ , він обчислює його об'єм $V$ і кількість слів $W$ , знаходить його індекс $I$ у відповідній множині $S$ (індекс серед усіх впорядкованих повідомлень об'єму $V$ з $W$ словами) і надсилає лише три числа: $V, W$ та $I$ !

Департамент національної безпеки доклав вже чималих зусиль, але відтепер вони потребують вашої допомоги для декодування повідомлень, які відправляє шпигун! Тобто, знаючи $V, W$ та $I$ , ви повинні розшифрувати повідомлення або визначити, що такого повідомлення не існує.

Вхідні дані

Перший рядок містить одне ціле число $T$ $(1 \leq T \leq 200)$ (1 \leq T \leq 200) — кількість тестових випадків. Кожен набір даних складається з рядка з трьома цілими числами: об'єм повідомлення $V$ $(1 \leq V \leq 75)$ (1 \leq V \leq 75), кількість слів $W$ $(1 \leq W \leq 20)$ (1 \leq W \leq 20) та індекс повідомлення $I$ $(1 \leq I \leq 1 0^{18})$ (1 \leq I \leq 10^{18}).

Вихідні дані

Для кожного тесту виведіть один рядок з розшифрованим повідомленням, або "Corrupted!", якщо для заданих параметрів не існує жодного допустимого повідомлення.

Приклади

Приклад

2
7 2 3
2 1 2

aa a
Corrupted!

Приклад 1

Примітка

У першому тестовому випадку впорядкована множина повідомлень об'єму $7$ , які містять $2$ слова: ${a aa, a c, aa a, b b, c a}$ \{\texttt{a\ aa},\ \texttt{a\ c},\ \texttt{aa\ a},\ \texttt{b\ b},\ \texttt{c\ a}\}; третім повідомленням є "aa a". У другому тестовому випадку впорядкована множина повідомлень об'єму $2$ , які містять $1$ слово: ${a}$ ; у множині лише одне повідомлення, а запитується індекс $2$ , — щось явно пішло не так!