eolymp
bolt
Try our new interface for solving problems
Problems

Система счисления - 2

Система счисления - 2

Time limit 1 second
Memory limit 64 MiB

Напишите программу, переводящую запись числа между двумя произвольными системами счисления. На вход программа получает три величины: n, A, k, где n и k – натуральные числа от 2 до 36: основания системы счисления, A – число, записанное в системе счисления с основанием n, 0 < A < 2^31.

Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей. Цифры записываются следующими символами: '0', '1', '2', ..., '9', 'A', 'B', 'C', ..., 'Z'.

Input data

Всего 3 строки во входном файле: В первой строке – число n, 2n36. Во второй строке – число A, записанное в системе счисления с основанием n, 0 < A < 2^31. В третьей строке – число k, 2k36.

Output data

Выведите число, записанное в системе счисления с основанием k.

Examples

Input example #1
10
19
2

Output example #1
10011