Cho một số nguyên dương ~ N ~ và một cơ số ~ B ~ (với ~ 2 \leq B \leq 36 ~). Hãy chuyển số ~ N ~ từ hệ thập phân sang hệ cơ số ~ B ~.

Trong hệ cơ số ~ B ~, các chữ số được biểu diễn như sau:

• Các giá trị từ 0 đến 9 được biểu diễn bởi các ký tự '0' đến '9'
• Các giá trị từ 10 đến 35 được biểu diễn bởi các ký tự in hoa từ 'A' đến 'Z'

Input

Gồm một dòng duy nhất chứa hai số nguyên ~ N ~ và ~ B ~ (~ 1 \leq N \leq 10^{18} ~, ~ 2 \leq B \leq 36 ~).

Output

In ra một dòng duy nhất là chuỗi biểu diễn số ~ N ~ trong hệ cơ số ~ B ~.

Ví dụ

Input 1

255 16

Output 1

FF

Input 2

1000 2

Output 2

1111101000

Input 3

123456789 36

Output 3

21I3V9

Chấm điểm

• Subtask 1 (30 điểm): ~ N \leq 10^6 ~, ~ B \leq 16 ~.
• Subtask 2 (70 điểm): ~ N \leq 10^{18} ~, ~ B \leq 36 ~.