from sage.all import *


def F(a, b):
    sequence = [2 * a, b]
    while sequence[-1] > 1:
        sequence.append(-sequence[-2] % sequence[-1])
    sequence[0] /= 2
    if sequence[-1] == 0:
        sequence = sequence[:-1]
    return sequence


def sliding_window_sum(vals: list[int]) -> list[int]:
    ret = []
    for idx, i in enumerate(vals[1:]):
        if idx == len(vals) - 2:
            ret.append(i + vals[0])
        else:
            ret.append(i + vals[idx + 2])
    return ret


def subdivide_at(struct: list[int], i: int) -> list[int]:
    x = 0
    if i >= len(struct) - 1:
        x = struct[-1] + struct[0]
    else:
        x = struct[i] + struct[i + 1]
    return insert_at(list(struct), i + 2, x)


def subdivide_everywhere(struct: tuple) -> list[tuple]:
    ret = []
    for i in range(1, len(struct)):
        ret.append(tuple(subdivide_at(struct, i)))
    return ret


def find_all_subdivisions(struct: tuple, until: int) -> list[tuple]:
    lst: list[tuple] = [struct]
    for i in range(len(struct), until):
        s = set()
        for a in lst:
            for variation in subdivide_everywhere(a):
                s.add(variation)
        lst = list(s)
    return lst


def find_all_subdivisions(struct: tuple, until: int) -> list[tuple]:
    lst: list[tuple] = [struct]
    for i in range(len(struct), until):
        s = set()
        for a in lst:
            for variation in subdivide_everywhere(a):
                s.add(variation)
        lst = list(s)
    return lst


def divides(a: int, b: int) -> bool:
    return a % b == 0


def choose(n: int, k: int) -> int:
    if k > n: return 0
    if k == 0: return 1
    if k == 1: return n
    return factorial(n) / (factorial(n - k) * factorial(k))


def ballot(k: int, l: int) -> int:
    return (k - l + 1) / (k + 1) * binomial(k + l, k)


def callot(n: int, k: int) -> int:
    return ballot(n - 1, n - k)


def insert_at(arr: list, i: int, x) -> list:

    return arr[0:i] + [x] + arr[i:]


def bident(a: int, b: int) -> list[int]:
    f_seq = [a, b]
    while f_seq[-2] != f_seq[-1] and f_seq[-1] != 1:
        f_seq.append(-f_seq[-2] % f_seq[-1])
    return f_seq


def catalan(n: int) -> int:
    return factorial(2 * n) / (factorial(n + 1) * factorial(n))


def mset_cardinality(n: int, l: int) -> int:
    return choose(n + l - 1, l)


def is_arithmetical_graph(struct) -> bool:
    G = struct[0].adjacency_matrix()
    r = struct[1]
    er = enumerate(r)

    def is_divisible(i):
        return sum(map(lambda j: j[1] * G[i[0]][j[0]], er)) % i[1] == 0

    return gcd(r) == 1 and all(is_divisible(i) for i in er)


def pairwise_sum(v1, v2):
    return list(map(lambda x: x[0] + x[1], zip(v1, v2)))


def create_hasse(x):
    divs = divisors(x)[::-1]
    s = defaultdict(list)
    for i in range(len(divs)):
        curr = divs[i]
        for j in divs[i + 1:]:
            if curr % j == 0:
                s[curr].append(j)

    def helper(div, cons):
        for c in cons:
            num = c[0]
            lst = c[1]
            full = c[2]
            if full or div == num:
                continue
            else:
                if div % num == 0:
                    lst.append(div)
                    full = len(lst) >= 3
        return cons

    consideration = []
    for div in divs[::-1]:
        consideration.append((div, [], False))
        consideration = helper(div, consideration)

    def index_ocurrences(elems, lst):
        indexes = []
        for elem in elems:
            if elem in lst:
                indexes.append(lst.index(elem))
        return indexes

    G = Graph()
    for idx, i in enumerate(consideration):
        lst = i[1][:len(factor(x))]
        indexes = []
        for index in index_ocurrences(lst, divs[::-1]):
            indexes.append((idx, index))

        G.add_vertex(idx)
        G.add_edges(indexes)
    return G


def characteristic(n: int, i: int) -> list[int]:
    ret = [0] * n
    ret[i] = 1
    return ret


def W(G: Graph, u: int, r: list[int]) -> set[int]:
    V = G.vertices()
    s = set()

    for w in V:
        for path in G.all_paths(u, w):
            if r[path[-1]] != 0 and all(r[vertex] == 0
                                        for vertex in path[1:-1]):
                s.add(w)

    return s


def algorithm_1(G: Graph, r: int, order: list[int]):
    r = vector(r)

    for i, u in enumerate(order, 1):
        e_u = vector(characteristic(len(r), u))
        r = r + sum(e_u * r[w] for w in W(G, u, r))

    return r


def cycle(n: int) -> Graph:
    if n == 2:
        G = Graph(multiedges=True)
        G.vertices(0, 1)
        G.add_edges([[0, 1], [0, 1], [0, 1]])
        return G
    G = Graph(multiedges=True)
    length = range(n)
    G.vertices(length)
    G.add_cycle(list(length))
    return G


def doubled_edge_cycle(n: int) -> Graph:
    assert n > 1
    G = cycle(n)
    G.add_edge(0, 1)
    return G