# def sum_num(s):
# 	summa = 0
# 	for i in s:
# 		if i.isdigit():
# 			summa += int(i)
# 	print(summa)

# sum_num('asd12312asdf')

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

# def get_body_mass_index(weight, height):
# 	index = weight/((height*0.01)**2)
# 	if index < 18.5:
# 		print('Недостаточная масса тела')
# 	elif 18.5 <= index <= 25.0:
# 		print('Норма') 
# 	else:
# 		print('Избыточная масса тела')

# get_body_mass_index(70, 170)		

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

# def check_password(psw):
# 	f1 = False
# 	digit_cnt = 0
# 	cap = False
# 	sim = False
# 	for i in psw:
# 		if i.isdigit():
# 			digit_cnt += 1
# 		if i.istitle():
# 			cap = True
# 		if i in "!@#$%":
# 			sim = True
# 	if (digit_cnt >= 3) and cap == True and sim == True and len(psw) >= 10:
# 		print('Perfect password')
# 	else:
# 		print('Easy peasy')

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~		
	
# def count_letters(s):
# 	cap_cnt = 0
# 	uncap_cnt = 0
# 	for i in s:
# 		if i.isalpha():
# 			if i.istitle():
# 				cap_cnt += 1
# 			else:
# 				uncap_cnt += 1
# 	print('Количество заглавных символов:', cap_cnt)
# 	print('Количество строчных символов:', uncap_cnt)

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

# def foo():
# 	print('function foo')

# a = foo()
# print(a)

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

# def find_duplicate(lst):
# 	my_list = []
# 	new_l = []
	
# 	for i in lst:
# 		if i not in my_list:
# 			my_list.append(i)

# 	for i in my_list:
# 		if lst.count(i) > 1:
# 			new_l.append(i)

# 	return new_l

# print(find_duplicate([1, 1, 1, 1, 1, 2, 2, 2, 2]))

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

def first_unique_char(s):
	s.lower()
	for i in range(len(s)):
		if s.count(s[i]) == 1:
			return i
	else:
		return -1
	
# print(first_unique_char('aasssddddddddq'))

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

def format_name_list(names: list):
	length = len(names)
	s = ""
	if length == 0:
		return ""
	elif length == 1:
		return names[0].get("name")
	elif length == 2:
		return names[0].get("name") + ' и ' + names[1].get("name")
	else:
		for i in range(len(names) - 1):
			s += names[i].get("name") + ', '
		
		return s[:-2] + " и " + names[-1].get("name")
			

# print(format_name_list([{'name': 'Bart'}, {'name': 'Lisa'}, {'name': 'Maggie'}, 
# 				  {'name': 'Homer'}, {'name': 'Marge'}]))

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

def get_domain_name(url : str):
	my_list = []
	if url.find("//") != -1:
		my_list = url.split("//")
		if my_list[1].find("www") != -1:
			my_list = my_list[1].split(".")
			return my_list[1]
			
		else:
			my_list = my_list[1].split(".")
			return my_list[0]
	else:
		my_list = url.split(".")
		return my_list[1]


# assert get_domain_name("http://google.com") == "google"
# assert get_domain_name("http://google.co.jp") == "google"
# assert get_domain_name("www.xakep.ru") == "xakep"
# assert get_domain_name("https://youtube.com") == "youtube"

# assert get_domain_name("http://github.com/carbonfive/raygun") =='github'
# assert get_domain_name("http://www.zombie-bites.com") == 'zombie-bites'
# assert get_domain_name("https://www.siemens.com") == 'siemens'
# assert get_domain_name("https://www.whatsapp.com") == 'whatsapp'
# assert get_domain_name("https://www.mywww.com") == 'mywww'
# print('Проверки пройдены')

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

def factorial(n):
    fact = 1
    for num in range(2, n + 1):
        fact *= num
    return fact

def trailing_zeros(n):
	s = str(factorial(n))[::-1]
	l = []
	for i in range(len(s)):
		if s[i] != '0':
			break
		else:
			l.append(s[i])

	return len(l)

# assert trailing_zeros(0) == 0
# assert trailing_zeros(6) == 1
# assert trailing_zeros(30) == 7
# assert trailing_zeros(12) == 2 

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

def count_AGTC(dna):
    return dna.count('A'), dna.count('G'), dna.count('T'), dna.count('C')


# assert count_AGTC('AGGTC') == (1, 2, 1, 1)
# assert count_AGTC('AAAATTT') == (4, 0, 3, 0)
# assert count_AGTC('AGTTTTT') == (1, 1, 5, 0)
# assert count_AGTC('CCT') == (0, 0, 1, 2)     
# print('Проверки пройдены')

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

def foo():
	"Эта функция делает что-то"
	pass

# print(foo.__doc__)

class Model:
	"""
	This is class model
	"""
	pass

# help(Model)
# print(Model.__doc__)

def get_even(lst, number):
	"""_summary_

	Args:
		lst (_type_): _description_
		number (_type_): _description_
	"""

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

# first : int = 100

# def add_numbers(a: int, b: int | float | str) -> int:
# 	return a + b

# print(add_numbers.__annotations__)

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

from typing import List, Dict, Tuple, Optional, Any, Union

def list_upper(lst: List[str]):
	for elem in lst:
		print(elem.upper())

# e: Any = 12
# e = "sdfsdf"

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

def first_repeated_word(s: str):
	"""Находит первый дубль в строке

	Args:
		s (str): строка

	Returns:
		str: первое повторяющееся слово
	"""
	l = s.split()
	d_index = dict()

	for i in range(len(l)):
		if (l.count(l[i]) > 1) and l[i] not in d_index.values():
			d_index.update({l.index(l[i], i+1, len(l)) : l[i]})
	
	if len(d_index) == 0:
		return None

	m = len(l)
	if m == 0:
		return None

	for key,value in d_index.items():
		if key < m:
			m = key

	return d_index.get(m)

# assert first_repeated_word("ab ca bc ab") == "ab"
# assert first_repeated_word("ab ca bc Ab cA aB bc") == "bc"
# assert first_repeated_word("ab ca bc ca ab bc") == "ca"
# assert first_repeated_word("hello hi hello") == "hello"
	
# print(first_repeated_word.__doc__)

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

def shift_letter(sim: str, shift: int):
	"""Функция сдвигает символ letter на shift позиций	"""
	code = ord(sim) - 97
	if shift >= 0:
		shift = shift - 26*(shift//26)
		if (code + 97 + shift) >= 122:
			return chr(code + 97 + shift - 26)
		else:
			return chr(code + 97 + shift)
	else:
		shift *= -1
		shift = shift - 26*(shift//26)
		if (code + 97 - shift) < 97:
			return chr(code + 97 + 26 - shift)
		else:
			return chr(code + 97 - shift)

# assert shift_letter('b', 2) == 'd'
# assert shift_letter('d', 1) == 'e'
# assert shift_letter('z', 1) == 'a'
# assert shift_letter('d', -2) == 'b'
# assert shift_letter('d', 26) == 'd'
# assert shift_letter('b', -3) == 'y'

def caesar_cipher(message: str, shift: int):
	"""Шифр цезаря"""
	my_str = ""
	for i in message:
		if i.isalpha():
			my_str += shift_letter(i, shift)
		else :
			my_str += i
	return my_str

# assert caesar_cipher('leave out all the rest', -1) == 'kdzud nts zkk sgd qdrs'
# assert caesar_cipher('one more light', 3) == 'rqh pruh oljkw'

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

MIN_DRIVING_AGE = 18

def allowed_driving(name: str, age: int) -> None:
    global MIN_DRIVING_AGE
    if (age >= MIN_DRIVING_AGE):
        print(name, "может водить")
    else:
        print(name, "еще рано садиться за руль")

# allowed_driving('tim', 17)

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

def get_word_indices(strings: list) -> dict:
	l = []
	d = {}
	for i in strings:
		l.append(i.lower().split())

	for i in range(len(l)):
		for j in l[i]:
			if j not in d.keys():
				d.setdefault(j, [i])
			else:
				short_list = d.get(j)
				short_list.append(i)
				d.update({j: short_list})
	return d
		

# assert get_word_indices(['Look at my horse', 'my horse', 'is amazing']) == {'look': [0], 'at': [0], 'my': [0, 1], 'horse': [0, 1], 'is': [2], 'amazing': [2]}
	
def foo(a: int, b: int) -> int:
	return a + b

# foo(b=2, 3)

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

def replace(text: str, old: str, new: str = ''):
	s = ''
	for i in text:
		if i == old:
			s += new
		else:
			s += i
	return s

# assert replace('Нет', 'т') == 'Не'
# assert replace('Bella Ciao', 'a') == 'Bell Cio'
# assert replace('nobody; i myself farewell analysis', 'l', 'z') == 'nobody; i mysezf farewezz anazysis'
# assert replace('commend me to my kind lord meaning', 'M', 'w') == 'commend me to my kind lord meaning'

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

def make_header(header: str, h_size : int = 1):
	return "<h" + str(h_size) + ">" + header + "</h" + str(h_size) + ">"

# print(make_header("hello", 6))
	
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~		

def append_to_list(value, my_list = None):
	if my_list is None:
		my_list = []
	my_list.append(value)
	print(my_list, id(my_list))

# append_to_list(77)

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

def create_matrix(size : int = 3, up_fill : int = 0, down_fill : int = 0):
	l = [[i if i == j else 0 for j in range(1, size + 1) ] for i in range(1, size + 1)]
	
	for i in range(0, size):
		for j in range(0, size):
			if j > i:
				l[i][j] = up_fill
			elif j < i:
				l[i][j] = down_fill

	return l

# print(create_matrix(size=4, up_fill=7, down_fill=9))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~		
# Передача значений

# *a, b, c = [True, 7, 'hello', 4, False, 5]
# print(a, b, c)

# s = [4, 10]
# print(list(range(*s)))

def f(a, b, c, d):
	print(a, b, c, d)

# Распаковка картежа
# a = ('hello', True, 78, [3, 4, 5])
# f(*a)

# Передача неопределенного количество неименованных аргументов
# Получится картеж
# def f(*args):
# 	s = 0
# 	for i in args:
# 		s += i
# 	return s

# print(f(1, 2, 3, 4, 5))

# Передача неопределенного количества именованных аргументов
# Получится словарь
# def f(**kwargs):
# 	for k, v in kwargs.items():
# 		print(k, v)

# f(a = 1, b = 5, c = 6, name = 123)

# Комбинация метовдов передачи
#
# def f(*args, **kwargs):
# 	print(args, kwargs)

# f(5, 4, 5, 6, 1, a = 1, b = 5, c = 6, name = 123)

# def outPrint(*args, sep = '#', end = '@'):
# 	print(args, sep, end)

# outPrint(1, 2, 3, 4, 5, end=111)

# Распаковка
# a = [1, 2, 3, 4]
# print(*a)

# a, b, *c = range(5)
# a, *b, c = 'No money', 'no honey'
# print(a, b, c)

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

def only_one_positive(*args):
    cnt = 0
    for i in args:
        if i >= 0:
            cnt += 1
    return cnt == 1

# print(only_one_positive(0,0,0,0,5430,0,0,0,0,0))

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

def print_goods(*args):
	cnt = 1
	for i in args:
		if type(i) == str and len(i) > 0:
			print(cnt, ". ", i, sep='')
			cnt += 1

	if cnt == 1:
		print("Нет товаров")

# print_goods(1, True, 'Грушечка', '', 'Pineapple') 


# def info_kwargs(**kwargs):
#     print('\n'.join([f'{k} = {v}' for k, v in sorted(kwargs.items())] -> ))

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

def info_kwargs(**kwargs):
	for k, v in sorted(kwargs.items()):
		print(f'{k} = {v}')

# info_kwargs(first_name="John", last_name="Doe", age=33)

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

def f(*args, **kwargs):
	print(args, kwargs)

# f(5, 4, 5, 6, 1, a = 1, b = 5, c = 6, name = 123)


def create_actor(**kwargs):
	d = {'name': 'Райан', 
	  	'surname': 'Рейнольдс', 
		'age': 46}
	d.update(kwargs)
	return d

# print(create_actor(name='Jack', age=20))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Рекурсия

def fact(x):
	if x == 1:
		return 1
	return fact(x-1)*x

# print(fact(4))

# Fibonacci
# def fib(n):
# 	if n == 1:
# 		return 0
# 	if n == 2:
# 		return 1
# 	return fib(n - 1) + fib(n - 2)

# print(fib(10))


# Палиндром
def palindrom(s):
	if len(s) <= 1:
		return True
	if s[0] != s[-1]:
		return False
	return palindrom(s[1:-1])

# print(palindrom("шалаш"))

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

def print_from(n: int):
	if n == 0:
		return
	print(n)
	return print_from(n - 1)

# print_from(5)

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

def print_to(n: int):
	if n < 1:
		return
	print_to(n - 1)
	print(n)

# print_to(3)

def req(l : list) -> None:
	if len(l) == 0:
		return
	req(l[1:])
	print(l[0], end=' ')

# req(list(map(int, input().split())))

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

def double_fact(n : int) -> int:
	if n == 1:
		return 1
	elif n == 2:
		return 2
	return n*double_fact(n - 2)

# print(double_fact(7))

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


def fib(n : int) -> int:
	if n == 0:
		return 0
	elif n == 1:
		return 1
	return fib(n - 1) + fib(n - 2)

# print(fib(7))

def tribonacci(n : int) -> int:
	if n == 0 or n == 1:
		return 0
	elif n == 2:
		return 1
	return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

# print(tribonacci(7))

def get_combin(n, k):
	if k == 0 or k == n:
		return 1
	return(get_combin(n - 1, k) + get_combin(n - 1, k - 1))

# print(get_combin(5, 2))

def ackermann(m, n):
	if m == 0:
		return n + 1
	if m > 0 and n == 0:
		return ackermann(m - 1, 1)
	return ackermann(m - 1, ackermann(m, n - 1))

# print(ackermann(3, 2))

def list_sum_recursive(l : list) -> int:
	if len(l) == 0:
		return 0
	elif len(l) == 1 :
		return l[0]
	return l.pop() + list_sum_recursive(l)

# print(list_sum_recursive([1, 2, 3]))

def flatten(l : list) -> list:
	if not l :
		return []
	if isinstance(l[0], list):
		return flatten(l[0]) + flatten(l[1:])
	return l[:1] + flatten(l[1:])

# print(flatten([[[[9]]], [1, 2], [[8]]]))

def st(s : str) -> str:
	if len(s) == 1 or len(s) == 2:
		return s
	return s[0] + '(' + st(s[1:-1]) + ')' + s[-1]

# print(st('123asfewrwfdsad4'))

def power(x, n):
	if n == 0:
		return 1
	if n < 0:
		return 1/power(x, -n)
	if n%2 == 0:
		return power(x, n//2)*power(x, n//2)
	else :
		return power(x, n - 1)*x

# print(power(2, -1))

a = [1, 2,[2, 3, 4, [3, 4,[2, 3], 5]]]

def rec(l, level=1):
	print(l, 'level = ', level)
	for i in l:
		if type(i) == list:
			rec(i, level + 1)

# rec(a)

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

def flatten_dict(nested : dict, prefix : str = '') -> dict:
	result = dict()
	for key, value in nested.items():	
		if type(value) == int:
			result.update({prefix + key: value})
		else:
			result.update(flatten_dict(value, prefix + key + '_'))		
	return result
	
nes = {'Germany': {'berlin': 7},
          'Europe': {'italy': {'Rome': 3}},
          'USA': {'washington': 1, 'New York': 4}}


# print(flatten_dict({'Q': {'w': {'E': {'r': {'T': {'y': 123}}}}}}))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Сортировка слиянием

def merge_two_list(a, b):
	c = []
	i = j = 0
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			c.append(a[i])
			i += 1
		else:
			c.append(b[j])
			j += 1
	if i < len(a):
		c += a[i:]
	elif j < len(b):
		c += b[j:]
	return c


def merge_sort(s):
	if len(s) == 1:
		return s
	middle = len(s)//2
	left = merge_sort(s[:middle])
	right = merge_sort(s[middle:])
	return merge_two_list(left, right)

# print(merge_sort([7, 5, 2 ,3, 9, 8, 6]))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Быстра сортировка

def quick_sort(s):
	if len(s) <= 1:
		return s
	
	elem = s[0]
	left = list(filter(lambda x: x < elem, s))
	center = [i for i in s if i == elem]
	right = list(filter(lambda x: x > elem, s))

	return quick_sort(left) + center + quick_sort(right)

# print(quick_sort([7, 5, 2 ,3, 9, 8, 6]))


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

# per = lambda a, b, c : a + b + c
# t = lambda x: 'positive' if x > 0 else 'negative'

# print(per(1, 2, 3))

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Сортировка по ключам

# a = [321, 32, 54, 3 ,56, 45, 23423, 423, 5435, 234]
# a.sort(key=lambda x: x//10%10)


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

# def linear(k, b):
# 	return lambda x: x*k+b

# graf1 = linear(2, 5)
# graf2 = linear(5, 3)
# print(graf1(3))
# print(graf2(9))


# starts_with = lambda s: True if s[0] == 'W' else False
# print(starts_with("World"))

# average = lambda *args: sum(*args)/len(*args) 
# print(average((1, 3, 6, 3)))

def get_days(month):
	if month in (1, 3, 5, 7, 8, 10, 12):
		print(31)
	elif month == 2:
		print(28)
	else:
		print(30)