Задача D. Системы счисления ≡

Условие

Дано число в системе счисления по основанию P. Требуется перевести его в систему счисления по основанию Q.

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

Первая строка входного файла содержит целые числа P и Q. Следующая строка содержит строку, представляющую собой запись числа в системе счисления по основанию P. Для записи числа используются цифры 0, 1, ..., 9, а также заглавные латинские буквы A, B, C, ..., X, Y, Z.

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

Выходной файл должен содержать представление того же числа в системе счисления по основанию Q. Формат тот же, что во входном файле.

Ограничения

2 ≤ P, Q ≤ 36

Число находится в пределах от 0 до 10⁹.

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

10 2
5

101

16 10
FF

255

2 3
110

20

36 10
1Z

71