Given a natural n, a basis b and a natural number c, we want to write n in basis b using exactly c characters, following the next format:

- If n in basis b has less than c digits, you must
add hashes on the left.
- If n in basis b has more of c digits, you must write c asterisks instead of n.

Your task is to write a program that, given a sequence of triplets n, b, c, prints for each one a line following this format.

Input

The input is a sequence of triplets n, b, c, with n ≥ 0, 2 ≤ b ≤ 10 and c > 0.

Output

For each triplet of the input, print a line according to the described format.

Observations

Strings are not allowed in this problem.

- We suggest you to use a function
*number_of_digits(n, b)*that, given two natural numbers |n| and |b| with 2 ≤ |b| ≤ 10, returns the number of digits that requires the representation of |n| in basis |b|. You must use recursion to write n in basis b (without the hashes).

Public test cases

**Input**

54321 10 5 4321 10 5 654321 10 5 9999 10 20 125 2 8 125 3 8 125 4 8 125 5 8 125 6 8 125 7 8 125 8 8 125 9 8 536870912 2 1 536870912 2 32 0 2 1 0 10 2

**Output**

54321 #4321 ***** ################9999 #1111101 ###11122 ####1331 ####1000 #####325 #####236 #####175 #####148 * ##100000000000000000000000000000 0 #0

Information

- Author
- Professorat de P1
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++