ROMAN = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
DIGITS = "0123456789abcdef"
PAIRS = {")": "(", "]": "[", "}": "{"}


def t01_reverse_words(s):
    return " ".join(reversed(s.split()))


def t02_roman_to_int(s):
    total = 0
    i = 0
    while i < len(s):
        if i + 1 < len(s) - 1 and ROMAN[s[i]] < ROMAN[s[i + 1]]:
            total += ROMAN[s[i + 1]] - ROMAN[s[i]]
            i += 2
        else:
            total += ROMAN[s[i]]
            i += 1
    return total


def t03_balanced(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack


def t04_rle(s):
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append(f"{s[i]}{j - i}")
        i = j
    return "".join(out)


def t05_binary_search(xs, target):
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def t06_merge_intervals(intervals):
    out = []
    for iv in sorted(intervals):
        if out and iv[0] < out[-1][1]:
            out[-1][1] = max(out[-1][1], iv[1])
        else:
            out.append(list(iv))
    return out


def t07_is_palindrome(s):
    t = [c.lower() for c in s if c.isalnum()]
    return t == t[::-1]


def t08_top_words(s, k):
    counts = {}
    for w in s.split():
        counts[w] = counts.get(w, 0) + 1
    ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))
    return [[w, n] for w, n in ranked[:k]]


def t09_flatten(xs):
    out = []
    for x in xs:
        if isinstance(x, list):
            out.extend(t09_flatten(x))
        else:
            out.append(x)
    return out


def t10_base_convert(n, base):
    out = []
    while n:
        out.append(DIGITS[n % base])
        n //= base
    return "".join(reversed(out))


def t11_common_prefix(words):
    if not words:
        return ""
    lo, hi = min(words), max(words)
    for i, ch in enumerate(lo):
        if i >= len(hi) or hi[i] != ch:
            return lo[:i]
    return lo


def t12_next_permutation(xs):
    a = list(xs)
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i < 0:
        return a
    j = len(a) - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])
    return a