Convert to Any Base

Write to_base(n, base) that returns the non-negative integer n written in the given base as a string. Digits above 9 use the uppercase letters A-F. Do not use format(), hex(), oct() or bin().

Examples

Input:  n = 255, base = 16
Output: "FF"

Input:  n = 10, base = 2
Output: "1010"

Input:  n = 100, base = 8
Output: "144"

Constraints

• 0 <= n <= 2**62
• 2 <= base <= 16
• to_base(0, base) is "0" for every base

Goals

• Generalise binary conversion to bases 2-16
• Map digit values 10-15 to letters A-F