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