codewars/courses/python_for_begginers/misc.py

from cmath import cos
from math import sin, cos
'''
number = int(input())
d = number%10
c = (number//10)%10
b = (number//100)%10
a = number//1000
print(a, b, c, d)
'''

# x = int(input())
# if x > 999 and x < 10000 and (x%17 == 0) and (x%7 == 0):
#     print("YES")
# else:
#     print("NO")


# x = int(input())
# x1 = x%10
# x2 = x//10%10
# x3 = x//100
# average = (x1 + x2 + x3) - max(x1, x2, x3) - min(x1, x2, x3)
# if (average == max(x1, x2, x3) - min(x1, x2, x3)):
#     print('Число интересное')
# else:
#     print('Число неинтересное')

# print(math.pi())


# n = int(input())
# counter = 1
# foo = 1
# for i in range(1, n + 1):
#     for j in range(1, int(counter/2) + 2):
#         print(j, end='')
#         foo = j
#     for foo in range(foo - 1, 0, -1):
#         print(foo, end='')

#     counter += 2
#     print()

# a = int(input())
# b = int(input())

# sum = 0
# max_sum = 0
# val = 0

# for i in range(a, b + 1):
#     for j in range (1, i + 1):
#         if i%j == 0:
#             sum += j
#     if sum >= max_sum:
#         max_sum = sum
#         val = i
#     sum = 0

# print(val, max_sum)

# ---------------------------------------------------------------------- 

# a = int(input())
# b = int(input())

# sum = 0
# max_sum = 0
# val = 0

# for i in range(a, b + 1):
#     for j in range (1, i + 1):
#         if i%j == 0:
#             sum += j
#     if sum >= max_sum:
#         max_sum = sum
#         val = i
#     sum = 0

# print(val, max_sum)

# ---------------------------------------------------------------------- 

# n = int(input())

# for i in range(1, n + 1):
#     print(i, end='')
#     for j in range (1, i + 1):
#         if i%j == 0:
#             print('+', sep='', end='')
#     print()

# ---------------------------------------------------------------------- 

# n = int(input())

# sum = 0
# f = 1

# for i in range(1, n + 1):
#     for j in range(1, i + 1):
#         f *= j
#     sum += f
#     f = 1

# print(sum)

# ---------------------------------------------------------------------- 

# a = int(input())
# b = int(input())
# flag = True

# if a == 1:
#     a += 1

# for i in range(a, b + 1):
#     for j in range (2, i):
#         if i%j == 0:
#             flag = False
#     if flag == True:
#         print(i)
#     else:
#         flag = True


# n = int(input())
# s = 0
# while n != 0:
#     if n % 2 == 0:
#         s += n % 10
#     n //= 10
# print(s)

# n = 8
# count = 0
# maximum = -10*12
# for i in range(n):
#     x = int(input())
#     if x % 4 == 0 and x != 0:
#         count += 1
#         if x >= maximum:
#             maximum = x
# if count > 0:
#     print(count)
#     print(maximum)
# else:
#     print('NO')

# n = 4
# count = 0
# maximum = -10**8
# for i in range(n):
#     x = int(input())
#     if x % 2 != 0:
#         count += 1
#         if x > maximum:
#             maximum = x
# if count > 0:
#     print(count)
#     print(maximum)
# else:
#     print('NO')

# n = int(input())
# if 3 <= n <= 19:
#     print('*'*19)
#     for i in range(n-2):
#         print('*                 *')
#     print('*'*19)

# ---------------------------------------------------------------------- 

# three_counter = 0
# last_digit_counter = 0
# last_digit_flag = False
# digit = 0
# even_ounter = 0
# sum = 0
# mul = 1
# greater_seven_counter = 0
# greate_seven_digit = 0
# sum_zero_five = 0

# n = int(input())

# last_digit = n%10

# while n != 0:

#     digit = n%10

#     if digit > 7:
#         mul *= digit
#         greater_seven_counter += 1
#         greate_seven_digit = digit

#     if digit > 5:
#         sum += digit

#     if digit % 2 == 0:
#         even_ounter += 1

#     if digit == 3:
#         three_counter += 1

#     if digit == 0 or digit == 5:
#         sum_zero_five += 1

#     if last_digit == digit:
#         last_digit_counter += 1

#     n //= 10

# print(three_counter)
# print(last_digit_counter)
# print(even_ounter)
# print(sum)
# if greater_seven_counter == 1:
#     print(greate_seven_digit)
# else:
#     print(mul)
# print(sum_zero_five)

# i = 1729
# first_flag = False
# second_flag = False

# x1, y1, x2, y2 = 0, 0, 0, 0

# for i in range(1729, 2000):
#     for a in range(1, i):
#         for b in range(a, i):
#             if first_flag == False:
#                 if a**3 + b**3 == i:
#                     first_falg = True
#                     x1 = a
#                     y1 = b
#             elif first_flag == True:
#                 if a**3 + b**3 == i:
#                     second_falg = True
#                     x2 = a
#                     y2 = b
#     if first_flag == second_flag == True:
#         print(i, x1, y1, x2, y2)
#         first_flag = False
#         second_flag = False
    

# i = 1729
# first_flag = False
# second_flag = False

# x1, y1, x2, y2 = 0, 0, 0, 0
# a, b, c, d = 1, 1, 1, 1

# for i in range(1729, 33000):
#     for a in range(1, 33):
#         for b in range(a, 33):
#             for c in range(b, 33):
#                 for d in range(c, 33):
#                     if a**3 + b**3 == c**3 + d**3:
#                         if (a**3 + b**3 == c**3 + d**3) and a != b and a != c and a != d:
#                             print(a**3 + b**3, a, b, c, d)
                        

# iter    - максимальное значение чисел, возводимых в куб. Здесь - это 33. Можно задать любое другое целое
# n        - кэш решений и массив для сортировки и вывода решений.
# n_ijkl - словарь для проверки решений.
# n_a, n_b - рабочие переменные.
# ijkl     - кортеж кортежей сумм пар кубов чисел в диапазоне до iter,
#             для сокращения вычислений за счёт исключения повторяющихся пар.
#             заготавливаем перед началом поика решений.

# from time import *   # для вычисления времени поиска решений
# iter,   n,  n_ijkl,  n_a,   n_b   =   33,   set(),  dict(),   0,   0
# t = perf_counter()      # сохраняем время начала вычислений
# ijkl = tuple([tuple([i ** 3 + j ** 3 for j in range(iter)]) for i in range(iter)]) 
# for i in range(1, iter):
#     for j in range(1, iter):
#         for k in range(1, iter):
#             for l in range(1, iter):
#                     n_a = ijkl[i][j]       # перебираем суммы кубов пар 
#                     n_b = ijkl[k][l]      # 
#                     if n_a == n_b and i != k and j != l and i != l and j != k: 
#                     # проверяем суммы кубов пар на равенство, а числа на неравенство.
#                     # если условие выполняется, производим записи в кэш решений и словарь с числами.
#                                   n.add(n_a)
#                                   n_ijkl[n_a] = (((i, j), i**3 + j**3), '=', (k**3 + l**3, (k, l)))
                                  
# # на основе кэша решений формируем упорядоченный массив решений.                       
# n = list(n)
# n.sort()

# # выводим время выполнения вычислений
# print(perf_counter() - t)

# # выводим чило полученных решений при заданном диапазоне чисел.
# print('N_res = ', len(n))

# # выводим в строчку:
# # - решение, числа первой пары, сумму кубов чисел первой пары, =,
# #    сумму кубов чисел второй пары, числа второй пары
# for r in n:
#     print(r, ' -> ', n_ijkl[r])

# n = int(input())
# my_list = []
# for i in range(n):
#     foo = int(input())
#     my_list.append(foo**3)
# print(my_list)

# -----------------------------------------------------------------------

# n_string = int(input())
# my_list = []
# for i in range(n_string):
#         my_list.extend(input())
# print(my_list)

# -----------------------------------------------------------------------

# my_string = input()
# my_list = my_string.split()
# print(*my_list, sep='\n')

# -----------------------------------------------------------------------

# my_string = input()
# my_list = my_string.split()
# for i in my_list:
#         print(i[0], end='.')

# -----------------------------------------------------------------------

# my_string = 'C:\Windows\System32\calc.exe'
# my_list = my_string.split('\\')
# print(*my_list, sep='\n')

# -----------------------------------------------------------------------

# my_string = input()
# my_list = my_string.split()
# for i in my_list:
#     print('+'*int(i))

# -----------------------------------------------------------------------

# sum = 0
# for i in range(50, 100 + 1):
#     sum += i**3
# print(sum)

# n = int(input())
# f = 1
# if n == 0:
#     print(1)
# else:
#     for i in range (1, n + 1):
#         f *= i
#     print(f)

# n = int(input())
# mo = 0
# ko = 0
# for i in range(n):
#     m, k = map(int, input().split())
#     if m > k:
#         m += 1
#     elif k > m:
#         k += 1
# if mo > ko:
#     print('Mishka')
# elif ko > mo:
#     print('Chris')
# else:
#     print('Friendship is magic!^^')

# n = int(input())
# s = []
# for i in range(n):
#     s.append(input().lower())

# for i in range(len(s)):
#     index = s[i].find('рок')
#     if index != -1:
#         print(i + 1, index + 1)

# n = int(input())
# s = []
# for i in range(n):
#     s.append(input().lower())

# for i in range(len(s)):
#     index = s[i].find('соль')
#     if index == -1:
#         if i != len(s) - 1:
#             print(s[i] + ', ', end='')
#         else:
#             print(s[i])


# n = int(input())
# s = []
# for i in range(n):
#     s.append(input())

# for i in range(len(s)):
#     if len(s[i]) > 10:
#         print(s[i][0], len(s[i]) - 2, s[i][-1], sep='')
#     else:
#         print(s[i])
    

# n, m = map(int, input().split())
# l = []
# sum_row = 0
# sum_col = 0
# sum_row_l = []
# sum_col_l = []

# for i in range(n):
#     l.append(list(map(int, input().split())))

# for i in range(n):
#     for j in range(m):
#         sum_row += l[i][j]
#     sum_row_l.append(sum_row)
#     sum_row = 0

# for j in range(m):
#     for i in range(n):
#         sum_col += l[i][j]
#     sum_col_l.append(sum_col)
#     sum_col = 0

# print(*sum_row_l)
# print(*sum_col_l)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# n = int(input())
# l = []
# for i in range(n):
#     l.append(list(map(int, input().split())))

# # n = 4
# #l = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
# # l = [[0, 0, 1, 0], [0, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]

# j = 0
# index = 1
# flag = True
# for i in range(n):
#     while j < n - index:
#         # print(l[i][j + index])
#         # print(l[j + index][i])
#         if l[i][j + index] != l[j + index][i]:
#             flag = False
#             break
#         j += 1
    
#     j = 0
#     index += 1

# if flag == True:
#     print("YES")    
# else:
#     print("NO")            

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# n, m = map(int, input().split())
# l = []
# foo = []
# sum = 0

# for i in range(n):
#     l.append(list(map(int, input().split())))

# for i in range(n):
#     for j in range(m):
#         sum += l[i][j]
#     foo.append(sum)
#     sum = 0

# print(max(foo))
# print(foo.index(max(foo)))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# n, m = map(int, input().split())
# l = []
# maximum = [0]*n
# col_index = [0]*n
# foo = 0

# for i in range(n):
#     l.append(list(map(int, input().split())))

# # n, m = 3, 3
# # l = [[3, 1, 2], [1, 3, 4],  [3, 3, 3]]

# for i in range(n):
#     for j in range(m):
#         if l[i][j] > foo:
#             foo = l[i][j]
#             maximum[i] = foo
#             # row_index[i] = i
#             col_index[i] = j

# foo = max(maximum)
# print(foo)          
# print(maximum.index(foo), col_index[maximum.index(foo)])

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# # n, m = map(int, input().split())
# # l = []

# n, m = 3, 3
# l = [[3, 1, 2], [1, 3, 4],  [3, 3, 3]]

# maximum = [0]*n

# # for i in range(n):
# #     l.append(list(map(int, input().split())))

# # n, m = 3, 3
# # l = [[3, 1, 2], [1, 3, 4],  [3, 3, 3]]

# for i in range(n):
#     maximum.append(sum(l[i]))

# print(maximum)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# n = int(input())
# l = []
# cnt = 0

# for i in range(n):
#     l.append(list(map(int, input().split())))

# for i in range (n):
#     for j in range(n):
#         if j == i:
#             continue
#         if l[i][0] == l[j][1]:
#             cnt += 1

# print(cnt)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# n, m = map(int, input().split())
# l = []
# cnt = 0

# l.append('.'*(m + 2))
# for i in range(n):
#     row = '.' + input() + '.'
#     l.append(row)
# l.append('.'*(m + 2))

# for i in range(n + 2):
#     print(l[i])

# for i in range(1, n + 1):
#     for j in range(1, m + 1):
#         if l[i - 1][j] == '.' and l[i][j + 1] == '.' and l[i + 1][j] == '.' and l[i][j - 1] == '.' and l[i][j] == '.':
#             cnt += 1                

# print(cnt)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# i_love_none = [None]*50
# print(i_love_none)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# t = ('asdfasd')
# print(type(t))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# from pprint import pprint # для красивого вывода словаря
# person = {}
# s = 'IVANOV IVAN 19 Samara SGU 4 5 5 5 4 3 5 3'

# s = s.split()
# print(s)
# print('-'*15)
# person['last_name'] = s[0]
# person['first_name'] = s[1]
# person['age'] = int(s[2])
# person['city'] = s[3]
# person['university'] = s[4]

# print(person)
# print('-'*15)

# person['marks'] = []
# for i in s[5:]:
#     person['marks'].append(int(i))

# pprint(person)

def test_list(l: list, val: int) -> None:
    l.append(4)
    val = 8

# a = 7
# my_list = [1, 2, 3]

# test_list(my_list, a)
# print(my_list, a)
    
def draw_triangle(fill, base):
    for i in range(1, int(base/2 + 1) + 1):
        print(fill*i)
    for i in range(int(base/2), 0, -1):
        print(fill*i)

# draw_triangle('*', 9)
        
def print_info(name, surname, patronymic):
    string = surname[0] + name[0] + patronymic[0]
    print(string.upper())


def print_digit_sum(num):
    ret = 0
    while num:
        ret += num%10
        num = num//10
    print(ret)

# print_digit_sum(1035)

def get_factors(num):
    l = []
    for i in range(1, num + 1):
        if num%i == 0:
            l.append(i)
    return l

# print(get_factors(10))

def number_of_factors(num):
    return len(get_factors(num))
               
# print(number_of_factors(10))

def find_all(target, symbol):
    l = []
    s = ""
    for i in range(len(target)):
        if target[i] == symbol:
            l.append(i)
    return l

# print(find_all('sdfwerasdfqfaf', 's'))

def merge(list1, list2):
    list1.extend(list2)
    list1.sort()
    return list1

# print(merge([1, 2, 3], [5, 6, 7, 8]))

def is_prime(num):
    cnt = 0
    for i in range(1, num + 1):
        if num%i == 0:
            cnt += 1
    return cnt == 2

def get_next_prime(num):
    index = 1
    while is_prime(num + index) == False:
        index += 1
    return num + index

# print(get_next_prime(7))


# его длина не менее 8 символов; 
# он содержит как минимум одну заглавную букву (верхний регистр); 
# он содержит как минимум одну строчную букву (нижний регистр);
# он содержит хотя бы одну цифру.

def is_password_good(password):
    up_flag = False
    low_flag = False
    dig_flag = False
    for i in password:
        if up_flag == False: up_flag = i.istitle()
        if low_flag == False: low_flag = i.islower()
        if dig_flag == False: dig_flag = i.isdigit()

    return len(password) >= 8 and up_flag and low_flag and dig_flag

# print(is_password_good("sfasddfDeqwe"))


def is_one_away(word1, word2):
    cnt = 0
    len_flag = len(word1) == len(word2)

    if len_flag:
        for i in range(len(word1)):
            if word1[i] != word2[i]:
                cnt +=1

    return len_flag and cnt == 1
    
# print(is_one_away("aab", "abc"))


def is_palindrome(text:str):
    s = ''
    flag = True
    for i in range(len(text)):
        if text[i].isalpha():
            s += text[i].lower()

    for i in range(len(s)//2):
        if s[i] != s[-1 - i]:
            flag = False

    return flag


# print(is_palindrome("BEEGEEK"))



    # число a – должно быть палиндромом;
    # число b – должно быть простым;
    # число c – должно быть четным.

def is_number_palindrome(num):
    orig = num
    new = 0
    while num:
        num, d = divmod(num, 10)
        new = new*10 + d

    return new == orig

def is_simple(num: int):
    cnt = 0
    for i in range(1, num + 1):
        if num%i == 0:
            cnt += 1
    return cnt == 2


def is_valid_password(password: str):
    if password.count(":") != 2:
        return False
    a, b, c = map(int, password.split(":"))

    return is_number_palindrome(a) and is_simple(b) and c%2 == 0

# print(is_valid_password("24422442:181:890000"))


# )(())()(()())((()))()(())
def is_correct_bracket(text: str):
    index = 0
    for i in text:
        if i == '(':
            index += 1
        elif i == ')':
            index -= 1
        if index < 0: return False
    return index == 0

# print(is_correct_bracket("()(())()((())((()))()(())"))


def convert_to_python_case(text: str):
    s = text[0].lower()
    for i in text[1:]:
        if i.isupper():
            s = s + '_' + i.lower()
        else:
            s += i
    return s

# print(convert_to_python_case('ThisIsCamelCased'))
# print(convert_to_python_case('IsPrimeNumber'))


def solve(a, b, c):
    d = b**2 - 4*a*c
    if d == 0:
        return -1*b/(2*a), -1*b/(2*a)
    x1 = (-1*b + d**0.5)/(2*a)
    x2 = (-1*b - d**0.5)/(2*a)
    if x1 <= x2:
        return x1, x2
    else:
        return x2, x1

# вызываем функцию
# x1, x2 = solve(1, 2, 1)
# print(x1, x2)
    

def number_to_words(num):
    d = {1: 'один', 2: 'два', 3: 'три', 4: 'четыре', 5: 'пять', 6: 'шесть', 7: 'семь', 8: 'восемь', 9: 'девять', 10: 'десять', 11: 'одиннадцать', 12: 'двенадцать', 13: 'тринадцать', 14: 'четырнадцать', 15: 'пятнадцать', 16: 'шестнадцать',17: 'семнадцать', 18: 'восемнадцать', 19: 'девятнадцать', 20: 'двадцать', 30: 'тридцать', 40: 'сорок', 50: 'пятьдесят', 60: 'шестьдесят', 70: 'семьдесят', 80: 'восемьдесят', 90: 'девяносто'}
    ans = ""
    f, s = num//10, num%10
    if num > 20:
        ans = d[f*10] + " "
        if s:
            ans += d[s]
    else:
        ans = d[num]
    return ans
   

def get_month(language, number):
    lng_ru = ['январь', 'февраль', 'март', 'апрель', 'май', 'июнь', 'июль', 'август', 'сентябрь', 'октябрь', 'ноябрь', 'декабрь']

    lng_en = ['january', 'february', 'march', 'april', 'may', 'june', 'july', 'august', 'september', 'october', 'november', 'december']

    if language == 'ru':
        return lng_ru[number - 1]
    else:
        return lng_en[number - 1]
    
# print(get_month('ru', 1))

def is_magic(date):
    day, month, year = map(int, date.split('.'))
    year = year%100
    return day*month == year

# print(is_magic('10.06.1960'))

from string import ascii_lowercase

def is_pangram(text):
    flag = True
    text = text.lower()
    for i in ascii_lowercase:
        if i not in text:
            flag = False
    return flag

# print(is_pangram('Jackdaws love my big sphinx of quartz'))
# print(is_pangram('The jay pig fox zebra and my wolves quack'))
# print(is_pangram('Hello world'))