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)