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'))