解锁未知，未来循迹。

Description

小玖进入了一处神秘空间。

她发现了一个密码锁，锁边上有一张字条：

为了解开锁，你需要设计一个程序，使得我输入十进制整数 $n,k,x$，你要输出 $n$ 在 $k$ 进制下从低到高第 $x$ 位的数码。

小玖并不会写程序，于是她远程连线，求助小蕊。

可是小蕊说她正在大叫，所以你要帮助小玖。

Format

Input

一行三个整数 $n,k,x$。

Output

一行一个数码，为 $n$ 在 $k$ 进制下从低到高第 $x$ 位的数码。

特别地，如果 $n$ 在 $k$ 进制下不足 $x$ 位，请你输出隐含的前导 $0$。

Samples

5 2 4

0

16 3 2

2

25 -3 5

1

Explanation

对于样例一，$(5)_{10}=(101)_2=1\times5^2+0\times5^1+1\times5^0$，从低到高第 $4$ 位为隐含的前导 $0$。

对于样例二，$(16)_{10}=(121)_3=1\times 3^2+2\times3^1+1\times 3^0$，从低到高第 $2$ 位为 $2$。

对于样例三，$(25)_{10}=(12011)_{-3}=1\times(-3)^4+2\times(-3)^3+0\times(-3)^2+1\times(-3)^1+1\times(-3)^0$，从低到高第 $5$ 位为 $1$。

Limitation