시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

Given relatively prime positive integers p > q, any positive integer, n, can be written uniquely as a linear combination of powers of (p/q) with coefficients in the range 0 … (p-1).

n = a0 + a1*(p/q) + a2*(p/q)2 + …

For instance,

15 = 2*(3/2)4 + 1*(3/2)3 + 0*(3/2)2 + 1*(3/2) + 0

15 = 4*(7/4)2 + 1*(7/4) + 1

Write a program to find the base (p/q) expansion of an integer n. As digits for the base (p/q) expansion, use the characters 0-9, then A-Z, then a-z.

입력

Input consists of a single line that contains 3 space separated decimal values. They are the numerator p (3 <= p <= 62) of the fractional base, followed by the decimal denominator q (2 <= q <= (p-1)) of the fractional base, followed by the positive integer n to be represented in base (p/q). Values of p, q, and n will be chosen so that p and q are relatively prime, the expansion has at most 40 digits and n will fit in a 32-bit unsigned integer.

출력

Your program should produce a single output line containing a string of digits [0-9,A-Z,a-z] with the most significant digit first.

예제 입력 1

3 2 15

예제 출력 1

21010

예제 입력 2

7 4 15

예제 출력 2

411

예제 입력 3

59 31 987654321

예제 출력 3

V3bkX4XQVKITSN3ur6TAGF1pSFi