import numpy as np
from functools import cache


@cache
def number_of_binary_trees(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        N = 0
        for i in range(0, n):
            N += number_of_binary_trees(i) * number_of_binary_trees(n-i-1)
        return N

@cache
def number_of_full_binary_trees(n):
    if n <= 1:
        return 1
    elif n%2 == 0:
        return 0
    else:
        N = 0
        # Only odd numbers possible.
        for nleft in range(1, n, 2):
            nright = n-1-nleft
            N += number_of_full_binary_trees(nleft) * number_of_full_binary_trees(nright)
        return N

@cache
def circle_chords(n):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        N = 0
        for i in range(0, n):
            for j in range(i+1, n):
                left = j - i - 1
                right = n - 2 - left
                N += 1 + circle_chords(left) * circle_chords(right)
        return N

def subset_sum(s, n, tot):
    if tot == 0:
        return True
    if n < 0 or tot < 0:
        return False

    incl = subset_sum(s, n-1, tot-s[n])

    if incl:
        return True

    excl = subset_sum(s, n-1, tot)
    return excl

def equal_partitions(s):
    S = sum(s)
    if len(s) == 0 or S % 2 == 1:
        return False
    return subset_sum(s, len(s)-1, S/2)

def find_min_matrix_path(mat, i=0, j=0, mem=dict()):
    # Find min-cost path from (0,0) to mat.shape - (1,1)
    if (i+1, j+1) == mat.shape:
        return mat[i, j]
    if (i,j) in mem:
        return mem[i,j]
    if i < mat.shape[0]-1:
        via_right = find_min_matrix_path(mat, i+1, j, mem)
    else:
        via_right = 1e6
    if j < mat.shape[1]-1:
        via_down = find_min_matrix_path(mat, i, j+1, mem)
    else:
        via_down = 1e6
    if via_right < via_down:
        mem[i,j] = mat[i,j] + via_right
        return mem[i,j]
    else:
        mem[i,j] = mat[i,j] + via_down
        return mem[i,j]


def count_matrix_paths_with_cost(mat, cost, i=0, j=0):
    # Dest. is implicitly bottom right corner

    # Base case:
    if (i+1,j+1) == mat.shape:
        return cost == mat[i,j], [[(i,j)]]

    if i < mat.shape[0]-1:
        via_right, rp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i+1, j)
    else:
        via_right, rp = 0, []
    if j < mat.shape[1]-1:
        via_down, dp = count_matrix_paths_with_cost(mat, cost - mat[i,j], i, j+1)
    else:
        via_down, dp = 0, []
    paths = []
    if via_down+via_right > 0:
        paths = [[(i,j)] + p for p in rp+dp]
    return (via_down + via_right, paths)

def min_sum_partition(s, n, S1=0, S2=0):
    if n < 0:
        return S1, S2
    s11, s21 = min_sum_partition(s, n-1, S1+s[n], S2)
    s12, s22 = min_sum_partition(s, n-1, S1, S2+s[n])

    if abs(s11-s21) < abs(s12-s22):
        print(f"{s[n]} in S1")
        return s11, s21
    else:
        print(f"{s[n]} in S2")
        return s12, s22

def rodcut(L, lengths, prices, mem=dict()):
    if L < min(lengths):
        mem[L] = ([], 0)
        return [], 0
    if L in mem:
        return mem[L]
    best_l, best_p = [], 0
    for (l, p) in zip(lengths, prices):
        if L < l:
            continue
        l_, p_ = rodcut(L-l, lengths, prices)
        if p + p_ > best_p:
            best_p = p+p_
            best_l = [l] + l_
    mem[L] = [best_l, best_p]
    return best_l, best_p

@cache
def island_death(N, nstep, i=0, j=0):
    if i < 0 or j < 0 or i >= N or j >= N:
        return 1
    elif nstep <= 0:
        return 0
    else:
        return 1/4 * (
                island_death(N, nstep-1, i-1, j) +
                island_death(N, nstep-1, i+1, j) +
                island_death(N, nstep-1, i, j-1) +
                island_death(N, nstep-1, i, j+1))

def matrix_sum(mat):
    sums = np.zeros_like(mat)
    sums[0,0] = mat[0,0]
    for i in range(1, mat.shape[0]):
        sums[i, 0] = sums[i-1, 0] + mat[i, 0]
        for j in range(1, mat.shape[1]):
            sums[0, j] = sums[0, j-1] + mat[0, j]
            sums[i, j] = sums[i, j-1] + sums[i-1, j] + mat[i,j] - sums[i-1,j-1]
    return sums

def quick_matrix_sum(summat, c1, c2):
    a, b = c1
    c, d = c2
    corner, up, right = 0, 0, 0
    if a > 0 and b > 0:
        corner = summat[a-1, b-1]
    if b > 0:
        up = summat[c, b-1]
    if a > 0:
        right = summat[a-1, d]
    return summat[c,d] - up - right + corner

def max_k_submatrix(mat, k):
    summat = matrix_sum(mat)
    bestcoord, bestsum = None, -np.Inf
    for x in range(0, mat.shape[0]-k+1):
        for y in range(0, mat.shape[1]-k+1):
            cand = quick_matrix_sum(summat, (x,y), (x+k-1,y+k-1))
            if cand > bestsum:
                bestsum = cand
                bestcoord = (x, y)
    return bestcoord, bestsum

def target_sum(s, target):
    sums = np.zeros_like(s)
    for i in range(len(s)):
        sums[i] = sums[max(0, i-1)] + s[i]

    maxlen = -1
    firstix, lastix = None, None
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            if sums[j]-(sums[i-1] if i > 0 else 0) == target and (j-i+1) > maxlen:
                maxlen = j-i+1
                firstix, lastix = i, j
    return (firstix, lastix)