#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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 10^{18} 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 10^{9} in base 10

Subtask 3 (20%) **A**,**B**<=10, the number will always be less than 10^{9} in base 10

Subtask 4 (45%) **A**,**B**<=36

## Sample Testcase 1

Input

101101 2 10Output

45

## Sample Testcase 2

Input

FFF 16 2Output

111111111111

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 5 | 10 | 1s | 32MB | Minimum |

2 | 30 | 10 | 1s | 32MB | Minimum |

3 | 20 | 10 | 1s | 32MB | Minimum |

4 | 45 | 10 | 1s | 32MB | Minimum |

5 | 0 | 2 | 1s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o base -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512