Decimal to base B

Convert a non-negative decimal number N to base B (2 to 36). Use digits 0–9 and then capital letters A–Z.

Reported in: Accenture (Aug 2022) (memory-based)

Input

One line: N and B.

Output

N written in base B.

Constraints

0 ≤ N ≤ 10^18; 2 ≤ B ≤ 36.

Example 1

Input:
718 12

Output:
4BA

Example 2

Input:
255 2

Output:
11111111

Hint: Repeatedly take N mod B as the next digit from the right, then divide N by B.

All coding practice