Problem Description
"All your base are belong to us" - CATS
As all your bases no longer belong to you anymore, it is no longer second nature for you to convert between bases
However, you are employed as a base converter and need to convert between bases. Write a program so that you don't lose your job
Input
The first line of the input contains a string, the number in the original base
The second line of the input contains two numbers A and B, the original base and the final base
Constraints
The number will be smaller than 1018 in base 10
All numbers are guaranteed to be positive and A and B>1
Output
A string representing the number in the new base
NOTE: For bases above 10, please use A,B,C,D,E,F etc. to represent 10,11,12,13,14,15 etc. respectively
Subtasks
Subtask 1 (5%) A = B
Subtask 2 (30%) A = 10, B<=10, the number will always be less than 109 in base 10
Subtask 3 (20%) A,B<=10, the number will always be less than 109 in base 10
Subtask 4 (45%) A,B<=36
Sample Testcase 1
Input
101101
2 10
Output
45
Sample Testcase 2
Input
FFF
16 2
Output
111111111111