I. Base62
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

As we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of $$$2$$$ to $$$62$$$. The symbols '0' – '9' represent zero to nine, and 'A' – 'Z' represent ten to thirty-five, and 'a' – 'z' represent thirty-six to sixty-one. Now you need to convert some integer $$$z$$$ in base $$$x$$$ into base $$$y$$$.

Input

The input contains three integers $$$x, y~(2 \le x, y \le 62)$$$ and $$$z~(0 \le z \lt x^{120})$$$, where the integer $$$z$$$ is given in base $$$x$$$.

Output

Output the integer $$$z$$$ in base $$$y$$$.

Example
Input
16 2 FB
Output
11111011