# a = [42, 23, 66, 42, 93, 47, 30]
# b = 'dsf aaerwq dfasdf '
# c = ('sdf', 'sdqwet', 'ghetrertg')

# метод .sort возвращает None
# new_list = a
# new_list = new_list.sort()
# print(new_list)

# Принимает любую итерабельную последовательность
# Не изменяет начальную коллекцию
# Возвращает список
# sorted(a)


# sorted_string = sorted(b, reverse=True)
# sorted_tuple = sorted(c)

# print(sorted_string)
# print(sorted_tuple)
# print(sorted(a))


# Сортировка будет происходить по двум признакам последовательно
# def foo(x):
# 	return x%10, x//10%10

# print(sorted(a, key=foo))


# my_list_1 = ['ZZZ 5', 'aaa 7', 'BBB 23', 'www 45', 'EEE 5', 'ddd 5']

# print(sorted(my_list_1, key = str.lower))
# print(sorted(my_list_1, key = lambda x: (int(x.split()[1]), x.split()[0].lower() )))

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


# subject_marks = [('English', 88), ('Science', 90), ('Maths', 97), ('Physics', 93),('History', 82)]

# subject_marks = [('English', 88), ('Science', 90), ('Maths', 88),
#                  ('Physics', 93), ('History', 78), ('French', 78),
#                  ('Art', 78), ('Chemistry', 88), ('Programming', 91)]

# subject_marks = sorted(subject_marks, key = lambda x: x[1])
# for key, value in subject_marks:
# 	print(key, value)


# subject_marks = sorted(subject_marks, key = lambda x: x[1], reverse=True)
# for key, value in subject_marks:
# 	print(key, value)


# subject_marks = sorted(subject_marks, key = lambda x: (-x[1], x[0]))
# for key, value in subject_marks:
# 	print(key, value)

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

# models = [{'make': 'Nokia', 'model': 216, 'color': 'Black'},
#           {'make': 'Mi Max', 'model': 2, 'color': 'Gold'},
#           {'make': 'Samsung', 'model': 7, 'color': 'Blue'},
#           {'make': 'Apple', 'model': 10, 'color': 'Silver'},
#           {'make': 'Oppo', 'model': 9, 'color': 'Red'},
#           {'make': 'Huawei', 'model': 4, 'color': 'Grey'},
#           {'make': 'Honor', 'model': 3, 'color': 'Black'}]

# models = sorted(models, key=lambda x: x.get('color'))

# for i in models:
# 	print("Производитель: ", i.get('make'), ", модель: ", i.get('model'), ", цвет: ", i.get('color'), sep='')
	


# for i in sorted(models, key=lambda x : models.)

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

# my_list = []

# while True:
# 	st = input()
# 	if st == 'конец':
# 		break
# 	my_list.append(st.rpartition(':'))

# for i in sorted(my_list, key=lambda x: -int(x[2])):
# 	print(i[0])

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

# n = int(input())
# my_list = []
# my_dict = {}

# for i in range(n):
# 	st = input()
# 	if my_dict.get(st) == None:
# 		my_dict.update({st: 1})
# 	else:
# 		my_dict.update({st: my_dict.get(st) + 1})

# for key, value in my_dict.items():
# 	my_list.append([key, value])

# my_list = sorted(my_list, key=lambda x: x[1])

# print(my_list[-1][0], ', ', my_list[-1][1], sep='')
# print(my_list[0][0], ', ', my_list[0][1], sep='')

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

# print(type(input().split()))

# my_dict = {}
# n = input()
# for i in range(n):
# 	st = input().split()

def sort_1():
    fone_book = {}
    req_list = []
    rec_cnt = int(input())
    for i in range(rec_cnt):
        record = input().split()
        if record[1] not in fone_book.keys():
            fone_book[record[1]] = [record[0]]
        else:
            tmp = fone_book[record[1]]
            tmp.append(record[0])
            fone_book[record[1]] = tmp

    req_cnt = int(input())
    for i in range(req_cnt):
        req_list.append(input())
    for i in req_list:
        if i in fone_book.keys():
            print(*fone_book[i])
        else:
            print('Неизвестный номер')
    
# sort_1()

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

def sort_2():
    birthday_book = {}
    req_list = []
    rec_cnt = int(input())
    for i in range(rec_cnt):
        record = input().split()

        if record[2] not in birthday_book.keys():
            birthday_book[record[2]] = [[record[0], record[1]]]
        else:
            tmp = birthday_book[record[2]]
            tmp.append([record[0], record[1]])
            birthday_book[record[2]] = tmp

    req_cnt = int(input())
    for i in range(req_cnt):
        req_list.append(input())

    for i in req_list:
        if i in birthday_book.keys():
            for j in birthday_book.get(i):
                print(j[0], end=' ')
            print()
        else:
            print('Нет данных')

# sort_2()

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

def sort_3():
    drivers = {}
    new_drivers = []
    in_str = ""
    in_data = []
    
    while True:
        int_str = input()
        if int_str == "конец":
            break
        in_data = int_str.split(", ")
        if in_data[0] not in drivers.keys():
            drivers[in_data[0]] = [int(in_data[1]), 1]
        else:
            drivers[in_data[0]] = [drivers.get(in_data[0])[0] + int(in_data[1]), drivers.get(in_data[0])[1] + 1]
    
    for key, value in drivers.items():
        new_drivers.append((key, value[0]/value[1]))

    new_drivers = sorted(new_drivers, key=lambda x: (-x[1], x[0][0])) 

    for i in new_drivers:
        print(i[0], i[1])

# sort_3()

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

# Сортировка пузырьком
def sort_bubble():
    a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6,  8, -2, 99]
    n = len(a)
    flag = True

    for i in range(n - 1):
        flag = True
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:                  # если порядок элементов пары неправильный
                a[j], a[j + 1] = a[j + 1], a[j]  # меняем элементы пары местами 
                flag = False
        if flag == True:
            break

    print('Отсортированный список:', a)

# sort_bubble()
    
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~    

# Сортировка выбором
def sort_selection():
    a = [78, -32, 5, 39, 58, -5, -63, 57, 72, 9, 53, -1, 63, -97,
        -21, -94, -47, 57, -8, 60, -23, -72, -22, -79, 90, 96, -41,
        -71, -48, 84, 89, -96, 41, -16, 94, -60, -64, -39, 60, -14,
        -62, -19, -3, 32, 98, 14, 43, 3, -56, 71, -71, -67, 80, 27,
        92, 92, -64, 0, -77, 2, -26, 41, 3, -31, 48, 39, 20, -30,
        35, 32, -58, 2, 63, 64, 66, 62, 82, -62, 9, -52, 35, -61,
        87, 78, 93, -42, 87, -72, -10, -36, 61, -16, 59, 59, 22,
        -24, -67, 76, -94, 59]

    n = len(a)
    
    new_a = []

    for i in range(len(a)):
        el = min(a)
        index = a.index(el)
        a.pop(index)
        new_a.append(el)

    print(new_a)

# sort_selection()

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

# Сортировка простыми вставками
def sort_simple_insertion():
    a = [1, 7, -3, 9, 0, -67, 34, 12, 45, 1000, 6,  8, -2, 99]
    n = len(a)

    for i in range(1, n): 
        elem = a[i]  # берем первый элемент из неотсортированной части списка
        j = i
        
        # пока элемент слева существует и больше нашего текущего элемента
        while j >= 1 and a[j - 1] > elem:
            # смещаем j-й элемент отсортированной части вправо
            a[j] = a[j - 1]
            # сами идём влево, дальше ищем место для нашего текущего элемента
            j -= 1

        # нашли место для нащего текущего элемента из неотсортированной части
        # и вставляем его на индекс j в отсортированной части
        a[j] = elem

    for i in range(1, n):
        elem = a[1] # первый элемент
        j = i       


    print('Отсортированный список:', a)
    
# sort_simple_insertion()
    
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~    

# Бинарный поиск
def binary_search(list, key):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        midVal = list[mid]
        if midVal == key:
            return mid
        if midVal > key:
            high = mid - 1
        else:
            low = mid + 1
    return 'not found :('