Interplanetary Base Conversion

The intergalactic shopping center hosts goods from various planets, each of which uses its own numeral system. This diversity makes price calculations complicated. Due to a very tight deadline given by party A, hdxrie has enlisted your help to develop a base conversion program.

You are given a number in base \(A\) and must convert it to its representation in base \(B\). Formally, if a number \(N\) in base \(A\) is represented as \(N = \sum_{i=0}^{k} d_i \times A^i\), then its representation in base \(B\) is the unique sequence of digits (using uppercase letters for digits above 9) that satisfies this equality.

inputFormat

The input consists of three lines:

• The first line contains an integer \(A\) (the source base, where 2 \(\le\) A \(\le\) 36).
• The second line contains an integer \(B\) (the target base, where 2 \(\le\) B \(\le\) 36).
• The third line contains a string \(S\) representing the number in base \(A\). The digits can be 0-9 and A-Z (in uppercase) as required.

outputFormat

Output a single line containing the representation of the given number in base \(B\) using uppercase letters for digits above 9. Do not output any leading zeroes.

sample

2
10
1011

11