Division#7409

Division

1 second

64 megabytes

Hard

Given two numbers $a$ and $b$ in the $31$ -ary numeral system, where it is known that $a$ is divisible by $b$ , your task is to determine the last $k$ digits of the quotient when $a$ is divided by $b$ , also expressed in the $31$ -ary numeral system.

Input

The first line contains a positive integer $a$ , represented in the $31$ -ary numeral system. This number can have up to one million digits. In this system, digits $0$ to $9$ represent themselves, while uppercase letters $A$ to $U$ represent digits $10$ to $30$ . The number $a$ does not have leading zeros.

The second line contains the number $b$ , formatted similarly to $a$ .

It is guaranteed that $a$ is divisible by $b$ without any remainder.

The third line contains the integer $k$ ( $1 \leq k \leq 1 0^{4}$ 1 \leq k \leq 10^4).

Output

Print exactly $k$ digits in the $31$ -ary numeral system, representing the last $k$ digits of the quotient. If the quotient has fewer than $k$ digits, prepend it with leading zeros. All letters in the output should be uppercase.

Examples

Example

8U
2
2

Example

9
2
1

Example

U
7
4

Example 1