Đổi cơ số

Máy tính lưu số ở nhiều hệ cơ số khác nhau. Cho số nguyên không âm N và cơ số B, hãy in biểu diễn của N trong hệ cơ số B. Các chữ số từ 10 đến 15 viết bằng chữ in hoa A–F (như hệ thập lục phân). N = 0 được biểu diễn là 0.

Gợi ý: chữ số cuối của biểu diễn là N mod B, phần còn lại là biểu diễn của N / B. Bài này phải làm bằng hàm đệ quy.

Input

Một dòng gồm hai số nguyên N B.

Constraints

• 0 ≤ N ≤ 10^18
• 2 ≤ B ≤ 16

Output

Một dòng là biểu diễn của N trong hệ cơ số B (không có số 0 thừa ở đầu).

Ví dụ

Ví dụ 1

Input

255 16

Output

FF

Ví dụ 2

Input

10 2

Output

1010