practice

from time import sleep

if __name__ != "__main__":
    print("external run, terminate.")
    exit(0)


class TextUtils:
    @staticmethod
    def slowPrint(message, delay=0.2):
        for let in message:
            sleep(delay)
            print(let, end="")


def test_slowprint():
    TextUtils.slowPrint("Hello, this should print nicely :)")


# Thread(target=test_slowprint).start()
def clamp(input, min, max):
    if input < min:
        return min
    if input > max:
        return max
    return input


class Solution:
    @staticmethod
    def findTime(self, S1, S2):
        time = 0
        index = 0

        for let in S2:
            cur_index = 0
            for key in S1:
                if key == let:
                    time += abs(index - cur_index)
                    index = cur_index
                    break
                cur_index += 1
        return time

    @staticmethod
    def substrCount(self, s, k):
        sub_count = 0
        max_index = len(s) - k + 1
        substring_array = []
        array_index = 0

        for index in range(max_index):
            subs = s[index:index + k]
            try:
                if substring_array[array_index] == subs:
                    next_letter = s[index + k + 1]
                    print("next: " + next_letter)
                    if subs.__contains__(next_letter):
                        subs += next_letter
            except IndexError:
                pass  # silent pass
            substring_array.append(subs)
            array_index += 1
            print(f"[{array_index}]: {subs}")
            print(substring_array)

        return sub_count

    @staticmethod
    def reformat_string(S, K):
        S = S.upper().replace("-", "")
        temp = ""
        group_array = []
        for lt in S[::-1]:
            if len(temp) == K:
                group_array.append(temp[::-1])
                temp = lt
            else:
                temp += lt

        if temp != "":
            group_array.append(temp[::-1])
        return '-'.join(group_array[::-1])

    @staticmethod
    def findAndReplace(S, Q, index, sources, targets):
        word_array = []
        active_index = 0
        skip = 0
        for key, letter in enumerate(S):
            if skip > 0:
                skip -= 1
                continue
            try:
                dna = False
                if key == index[active_index]:
                    if S[key: key + len(sources[active_index])] == sources[active_index]:
                        word_array.append(targets[active_index])
                        skip += (len(sources[active_index]) - 1)
                        active_index += 1
                        dna = True
                if not dna:
                    word_array.append(letter)
            except IndexError:
                pass
        return ''.join(word_array)

    @staticmethod
    def look_and_say(n):
        str = "1"
        row = 1
        while row < n:
            # print(f"[{row}] ",end='')
            str = Solution.parse_look(str)
            row += 1

        return str

    @staticmethod
    def parse_look(strn):
        # print(f"Parsing '{str}'")
        new_str = ""
        segment_array = []
        active_number = 0
        buffer = 0

        for num in strn:
            # print(f"In string we have: number {num} active {active_number} buffer {buffer}")
            if active_number != num:
                app = active_number != 0
                if app:
                    segment_array.append(str(buffer) + str(active_number))
                active_number = num
                buffer = 1
            else:
                buffer += 1
        segment_array.append(str(buffer) + str(active_number))

        new_str = ''.join(segment_array)
        return new_str

    @staticmethod
    def duplicates(arr, n):
        dict = {}
        out = []
        for i in range(len(arr)):
            if arr[i] in dict:
                dict[arr[i]] += 1
                if dict[arr[i]] == 1:
                    out.append(arr[i])
            else:
                dict[arr[i]] = 0
        if out:
            out.sort()
            return out
        return [-1]

    @staticmethod
    def rearrange(arr, n):
        positive = []
        negative = []
        output = []

        for num in arr:
            if num >= 0:
                positive.append(num)
            else:
                negative.append(num)
        max_size = max(len(positive), len(negative))
        for ind in range(max_size):
            try:
                output.append(positive[ind])
            except IndexError:
                pass
            try:
                output.append(negative[ind])
            except IndexError:
                pass

        return output

    @staticmethod
    def maxSumPath(arr1, arr2, m, n):
        start = arr1 if min(arr1[0], arr2[0]) in arr1 else arr2
        stop = arr2 if start == arr1 else arr1

        print(start, stop, sep=" :: ")

        ind = 0
        path = 0
        for el in start:
            print(el, end=", ")
            path += el
            try:
                ind = stop.index(el)
                break
            except ValueError:
                pass
        for el in stop[ind + 1:]:
            print(el, end=", ")
            path += el

        print("\n")
        return path

    @staticmethod
    def row_with_max_1s(arr, n, m):
        row_ones = []
        for row in arr:
            ones = 0
            for elem in row:
                if elem == 1:
                    ones += 1
            row_ones.append(ones)
        max_ones = -1
        winning_index = -1
        for key, r in enumerate(row_ones):
            if r > max_ones:
                max_ones = r
                winning_index = key

        if max_ones == 0:
            return -1
        return winning_index

    @staticmethod
    def areIsomorphic(str1, str2):
        first_letters = []
        second_letters = []
        for let in str1:
            if let not in first_letters:
                first_letters.append(let)

        for let in str2:
            if let not in second_letters:
                second_letters.append(let)

        if len(first_letters) != len(second_letters):
            return 0
        return 1

    @staticmethod
    def trappingWater(arr, n=None):
        heights = []
        collected_amount = 0
        for tower in arr:
            heights.append(tower)
        heights.sort()
        # print(heights)
        water_level = heights[-2]
        # print("water level ", water_level)

        for tower in heights:
            am = water_level - clamp(tower, 0, water_level)
            # print(tower, am)
            collected_amount += am
        return collected_amount

    @staticmethod
    def ExcelColumn(N):
        temp = N
        st = ''
        while temp:
            lt = temp % 26
            if lt == 0:
                st += 'Z'
                temp = temp // 26 - 1
            else:
                st += chr(64 + lt)
                temp = temp // 26
        return st[::-1]


sol = Solution()


def pangram(s):
    s = s.lower()
    let = [str(chr(x)) for x in range(97, 123)]
    used = {}
    # print(let, len(let))
    for letter in s:
        if letter in let:
            used[letter] = True
    return int(len(used) == 26)


def add_binary(A, B):
    rev_A = A[::-1]
    rev_B = B[::-1]
    sum = ""
    carry = 0

    for bit in range(max(len(rev_A), len(rev_B))):
        result = '0'
        try:
            op_1 = rev_A[bit]
        except IndexError:
            op_1 = '0'
        try:
            op_2 = rev_B[bit]
        except IndexError:
            op_2 = '0'

        # print(op_1, op_2)
        if op_1 == '0':
            if op_2 == '0':
                if carry == 1:
                    result = '1'
                    carry = 0
                else:
                    result = '0'

            elif op_2 == '1':
                if carry == 1:
                    result = '0'
                    carry = 1
                else:
                    result = '1'

        elif op_1 == '1':
            if op_2 == '0':
                if carry == 1:
                    result = '0'
                    carry = 1
                else:
                    result = '1'
            elif op_2 == '1':
                if carry == 1:
                    result = '1'
                    carry = 1
                else:
                    result = '0'
                    carry = 1
        sum += result

    if carry == 1:
        sum += "1"

    while sum[-1] == '0':
        sum = sum[:-1]

    return sum[::-1]