Задача G. Перевод длинных чисел

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Дано неотрицательное целое число a, записанное в системе счисления по основанию p. Требуется перевести это число в систему счисления по основанию q. Для представления цифр больше 9 используются заглавные латинские буквы (A — 10, B — 11, …, Z — 35).

Формат входного файла

Первая строка содержит числа p q. Вторая строка содержит строку, представляющую число (a)p.

Формат выходного файла

Выходной файл должен содержать единственную строку, представляющую (a)q без незначащих нулей в начале.

Ограничения

2 ≤ p, q ≤ 36, длина входной строки не превышает 1000 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 10
10010
18
2
31 17
AF2J5
6DG3BE

0.076s 0.012s 15