# Проверка числа на полиндром
# divmode(a, b) возвращает картеж: (целая часть от деления a на b, остаток)
def is_polindrom(x: int) -> bool:

    if x < 0:
        return False

    new = 0
    orig = x
    while x:
        x, d = divmod(x, 10)
        new = new*10 + d

    return new == orig    

# print(is_polindrom(121))


# Быстрое слияние двух отсортированных списков в один
def quick_merge(list1, list2):
    result = []
    p1 = 0 # указатель на первый элемент списка list1
    p2 = 0 # указатель на первый элемент списка list2

    while p1 < len(list1) and p2 < len(list2):
        if list1[p1] < list2[p2]:
            result.append(list1[p1])
            p1 += 1
        else:
            result.append(list2[p2])
            p2 += 1

    if p1 < len(list1):
        result += list1[p1:]
    else:
        result += list2[p2:]

    return result