В ходе игры «Зарница» Витя и Паша пересылают друг другу важные сообщения. Но для того, чтобы противник не смог их понять, сообщения кодируются. Для кодирования информации ребята используют латинский алфавит из 26 букв, все буквы заглавные. Слова кодируются следующим образом. Каждая буква в слове заменяется ее порядковым номером в алфавите, записанном в системе счисления с основанием Sys (2 <= Sys <= 36). Все полученные числа записываются подряд без пробелов. Если числа (порядковые номера букв) в заданной системе счисления могут иметь разную длину, то более короткие числа дополняются слева нулями до требуемой длины. Например, в десятичной системе счисления порядковый номер буквы A будет равен 1, а буквы Z – 26. Соответственно, при шифровании, к единице слева будет дописан ноль. То есть код буквы A будет 01, а код буквы Z – 26. Для усложнения возможной расшифровки сообщения противником, при кодировании разных слов, могут использоваться различные системы счисления. Основание использованной системы счисления, выраженное двухзначным десятичным числом дописывается справа к коду всего слова.
Например, слово AZ, при использовании десятичной системы счисления, будет закодировано как 012610, а при использовании троичной системы счисления будет закодировано как 00122203.
Напишите программу, которая будет расшифровывать закодированные сообщения.
На вход программе подается одно закодированное сообщение. Длина сообщения не более 100 символов. Программа должна вывести исходное слово.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
02201211011012003
|
HELLO
|
|
2
|
122130
|
ABBA
|