from typing import Callable, Any


def is_leap(year):
    if year % 4 == 0:
        if year % 100 == 0:
            if year % 400 == 0:
                return True
            else:
                return False
        else:
            return True
    else:
        return False


def runner_up(arr, reverse=False):
    if reverse:
        arr.sort(reverse=True)
    else:
        arr.sort()
    max = arr[-1]

    for i in range(len(arr) - 1, -1, -1):
        if arr[i] == max:
            continue
        else:
            return arr[i]
    return max


def second_lowest(records):
    arr = [a[1] for a in records]
    second_l = runner_up(arr, True)
    ans = [a[0] for a in records if a[1] == second_l]
    ans.sort()
    return ans


def average_mark(records, name):
    return sum(records[name]) / len(records[name])


def diagnoal_diff(square_matrix):
    sum1 = 0
    sum2 = 0
    n = len(square_matrix)
    for i in range(len(square_matrix)):
        sum1 = sum1 + square_matrix[i][i]
        sum2 = sum2 + square_matrix[i][n - i - 1]
    return abs(sum1 - sum2)


def substring_count(s, subs):
    ans = 0
    for i in range(len(s)):
        j = s[i:].find(subs)
        if j >= 0:
            ans = ans + 1
            if j == len(s) - 1:
                return ans
            else:
                return ans + substring_count(s[j + 1:], subs)
        else:
            return ans


def minion_game(s):
    ans = {}
    s = s.lower()
    vowels = ['a', 'e', 'i', 'o', 'u']

    # l = len(s)
    # for i in range(l):
    #     for j in range(l-i):
    #         if s[i:i+j+1] in ans:
    #             ans[s[i:i+j+1]] = ans[s[i:i+j+1]] + 1
    #         else:
    #             ans[s[i:i+j+1]] = 1
    # stuart = 0
    # kevin = 0
    # for k in ans:
    #     if k[0] in vowels:
    #         kevin = kevin + ans[k]
    #     else:
    #         stuart = stuart + ans[k]

    stuart = 0
    kevin = 0
    for i in range(len(s)):
        if s[i] in vowels:
            kevin = kevin + len(s) - i
        else:
            stuart = stuart + len(s) - i

    if stuart > kevin:
        return "Stuart " + str(stuart)
    else:
        if stuart == kevin:
            return "Draw"
        else:
            return "Kevin " + str(kevin)


def top_k_words_692(string_list, k):
    string_list = sorted(string_list)
    freq_dict = {}
    for i in string_list:
        if i in freq_dict:
            freq_dict[i] = freq_dict[i] + 1
        else:
            freq_dict[i] = 1

    freq_dict = dict(sorted(freq_dict.items(), key=lambda item: (item[1], ord(item[0][0]) * -1), reverse=True))
    ans = [None] * k
    for i in range(k):
        ans[i] = list(freq_dict)[i]

    return ans


def reorder_data_in_log_937(logs):
    letter_log = [l for l in logs if not l.split()[1].isdigit()]
    digit_log = [l for l in logs if l.split()[1].isdigit()]
    letter_log = sorted(letter_log, key=lambda x: (x.split(" ", 1)[1], x.split()[0]))
    return letter_log + digit_log


def run_length(input):
    if len(input) == 0:
        return ""
    running_character = input[0]
    running_count = 0
    output = ""

    for i in range(len(input)):
        if input[i] == running_character:
            running_count = running_count + 1
        else:
            output = output + str(running_count) + running_character
            running_character = input[i]
            running_count = 1
    return output + str(running_count) + input[-1]


def binary_search(input, element):
    left = 0
    right = len(input) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if input[mid] == element:
            return mid
        if input[mid] > element:
            right = mid - 1
        else:
            left = mid + 1
    return -1


def find_boundary_brute(input):
    if input[0]:
        return 0
    left = 0
    right = len(input) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if not input[mid]:
            left = mid + 1
        if input[mid]:
            while input[mid]:
                mid = mid - 1
            return mid + 1
    return -1


def find_boundary(input):
    ans = -1
    left = 0
    right = len(input) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if input[mid]:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans


def first_not_smaller(input, target):
    ans = -1
    left, right = 0, len(input) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if input[mid] >= target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans


def find_first_occurrence(input, target):
    ans = -1
    left, right = 0, len(input) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if input[mid] == target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans


def square_root(input):
    if input == 0:
        return 0
    ans = 0
    left, right = 1, input
    while left <= right:
        mid = left + (right - left) // 2
        if mid ** 2 > input:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans - 1


def find_min_rotated(input):
    for i in range(1, len(input)):
        if input[i] <= input[0]:
            return i
    return 0


def peak_of_mountain_array(input):
    ans = -1
    left = 0
    right = len(input) - 1
    while left <= right:
        mid = left + int((right - left) / 2)
        if input[mid] > input[mid + 1]:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans


def min_max_weight(weights, days):
    return 0


def countAnalogusArrays(consecutiveDifference, lowerBound, upperBound):
    arrayLength = len(consecutiveDifference) + 1
    counter = 0
    candidateArray = []

    for i in range(arrayLength):
        seed = lowerBound + i
        candidateArray.append(seed)
        currentMember = seed
        for j in range(lowerBound, upperBound + 1, 1):
            if len(candidateArray) == arrayLength:
                break
            nextMember = currentMember - consecutiveDifference[j - lowerBound]
            if nextMember > upperBound:
                candidateArray = []
                break
            if nextMember < lowerBound:
                candidateArray = []
                break
            candidateArray.append(nextMember)
            currentMember = nextMember
        if len(candidateArray) == arrayLength:
            counter = counter + 1
        candidateArray = []
    return counter

def minimalHeaviestSetA(arr):
    arr.sort(reverse = True)
    total_weight = sum(arr)
    running_total = 0
    ans = []

    for i in range(len(arr)):
        ans.append(arr[i])
        running_total = running_total + arr[i]
        if running_total > total_weight / 2:
            break
    ans.sort()
    return ans

def getNumberOfOptions(priceOfJeans, priceOfShoes, priceOfSkirts, priceOfTops, dollars):
    count = 0
    running_total = 0
    for a in priceOfTops:
        for b in priceOfSkirts:
            for c in priceOfJeans:
                for d in priceOfShoes:
                    if a + b + c + d <= dollars:
                        count = count + 1
    return count

def howManySwaps(arr):
    swaps = 0
    temp = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                swaps = swaps + 1
    return swaps

def storage(n, m, h, v):
    h_list = list(range(n))
    v_list = list(range(m))

    for i in h:
        del h_list[i - 1]
    for i in v:
        del v_list[i - 1]

    max_width = 0
    for i in range(len(h_list) - 1):
        if h_list[i+1] - h_list[i] > max_width:
            max_width = h_list[i+1] - h_list[i]

    max_height = 0
    for i in range(len(v_list) - 1):
        if v_list[i+1] - v_list[i] > max_height:
            max_height = v_list[i+1] - v_list[i]

    return abs(max_width * max_width)