# a,b,c = map(int,input().split())
#
# big = (b)if(a <= b)else(a)
# small= (b)if(a >= b)else(a)
# biggest= (c)if(big <= c)else(big)
# small2 = (big)if(big <= c)else(c)
#
# if small+small2 > biggest:
# print("yes")
# else:
# print("no")
#
# a,b = map(int,input().split())
#
# if b == 1 or b == 3 or b == 5 or b == 7 or b == 8 or b == 10 or b == 12:
# print("31")
# elif b == 2 and (a%400 == 0 or (a%4 == 0 and a%100 != 0)):
# print("29")
# elif b != 2:
# print("30")
# else:
# print("28")
# a,b = map(int,input().split())
#
# if b == 2:
# if :
# 29
# else:
# 28
# elif b == 4 or b == 6 or b == 9 or b == 11:
# 30
# else:
# 31
#
# while True:
#
# for i in range(5): # 0 to N-1
# print(i, end=' ')
# print()
#
# for i in range(1, 6): # N to M-1
# print(i, end=' ')
# print()
#
# for i in range(10, 20, 2): # N to M-1, jump K
# print(i, end=' ')
# print()
#
# for i in range(20, 10, -1):
# print(i, end=' ')
# print()
#
# data = ['Apple', 'Banana', 'Melon']
#
# for i in data:
# print(i, end=' ')
# print()
#
# a,b = map(int,input().split())
# big = (a)if(a> b)else(b)
# small = (b)if(a>b)else(a)
# for i in range(small,big+1):
# print(i, end = ' ')
# chr: char (X)
# a,b = input().split()
#
# a = ord(a) # chr > int
# b = ord(b)
# for i in range(a, b+1):
# print(chr(i),end = ' ')
# a = int(input())
#
# for i in range(1,a+1):
# print(i, end = ' ')
# a,b = map(int, input().split())
#
# for i in range(a,b+1):
# if i%2 == 1:
# print(i,end = " ")
# a = int(input())
# m = 0
#
# for i in range(1,a+1):
# m += i
#
# print(m)
# a = int(input())
# m = 0
# for i in range(1,a+1):
# if i%2 == 0:
# m += i
# print(m)
# a,b = map(int,input().split())
# m = 0
# for i in range(a,b+1):
# if i%3 == 0:
# m += i
# print(m)
# data = list(map(int, input().split()))
#
# for i in range(len(data)):
# print(data[i], end=' ')
# print()
# a = int(input())
# arr = list(map(int, input().split()))
# m = 0
# for i in range(len(arr)):
# m += arr[i]
# print(m)
# a = int(input())
# arr = list(map(int,input().split()))
# m = 0
# for i in range(len(arr)):
# if arr[i]%5 == 0:
# m += arr[i]
# print(m)
# a = int(input())
# arr = list(map(int,input().split()))
# m = 0
# for i in range(len(arr)):
# if arr[i]%2 != 0:
# m+=1
# print(m)
# a = int(input())
# arr = list(map(int,input().split()))
# max = 0
# for i in range(len(arr)):
# if(arr[i] >max):
# max = arr[i]
# print(max)
# a = int(input())
# m = 0
# for i in range(1,a+1):
# if a%i ==0:
# m +=1
# if m == 2:
# print("prime")
# else:
# print("not prime")
# a,b = map(int,input().split())
# sum = 1
# for i in range(1,b+1):
# sum *= a
# print(sum)
# sum = 0
# a,b = map(int,input().split())
# for i in range(a,b+1):
# if i%2 != 0:
# sum += i
# if i != a:
# print("+",end = "")
# print(i, end="")
# else:
# print(i,end = "")
# else:
# print("-",end="")
# print(i,end="")
# sum -= i
# print("=",end="")
# print(sum)
# m = 0
# arry = input()
# for i in range(len(arry)):
# if ord(arry[i]) <= 90 and ord(arry[i]) >= 65:
# m = ord(arry[i])+32
# print(chr(m),end="")
# elif ord(arry[i]) >= 97 and ord(arry[i]) <= 122:
# m = ord(arry[i])-32
# print(chr(m),end="")
# else:
# print(arry[i],end = "")
# a = int(input())
# for i in range(a):
# for j in range(a):
# if i == 0 or i == a-1:
# print("*",end ="")
# else:
# if j == 0 or j == a-1:
# print("*",end = "")
# else:
# print(" ",end = "")
# print("")
# a = int(input())
#
# for i in range(a):
# for j in range(a):
# if i == 0 or i == a-1:
# print("*",end = "")
# elif j == 0 or j == a-1:
# print("*",end="")
# elif i == j:
# print("*",end="")
# elif i == a-(j+1):
# if a%2 != 0 and i+1 != (1+a)//2:
# print("*",end ="")
# else:
# print("*", end="")
# else:
# print(" ",end="")
# print("")
# a = int(input())
# for i in range(1,a+1):
# for j in range(i):
# print("*",end ="")
# print()
# for i in range(a-1, 0,-1):
# for j in range(i):
# print("*",end ="")
# print()
# a = int(input())
# b = (a+1)//2
# for i in range(1,b+1):
# for j in range(1,a+1):
# if j <= b-i or j >= b+i:
# print(" ",end ="")
# else:
# print("*",end="")
# print()