2024-02-22

# n = int(input())## data = []### for i in range(n):#     x, y = map(int, input().split())#     data.append([i+1, x, y, x * 1000 + y])### for i in range(n):#     for j in range(n-1):#         if data[j][3] > data[j+1][3]:#             t = data[j]#             data[j] = data[j+1]#             data[j+1] = t##         elif data[j][1] == data[j+1][1]:### data.reverse()## for j in range(n):#     print(data[j][0], data[j][1], data[j][2])# n = int(input())## data = []## for i in range(n):#     x, y = map(int, input().split())#     data.append([i+1, x, y])## for i in range(n):#     for j in range(n-1):#         if data[j][1] < data[j+1][1]:#             t = data[j]#             data[j] = data[j+1]#             data[j+1] = t##         elif data[j][1] == data[j+1][1]:#             if data[j][2] < data[j+1][2]:#                 t = data[j]#                 data[j] = data[j+1]#                 data[j+1] = t## for j in range(n):#     print(data[j][0], data[j][1], data[j][2])# [1, 100, # n = int(input())
#
# data = []
#
#
# for i in range(n):
#     x, y = map(int, input().split())
#     data.append([i+1, x, y, x * 1000 + y])
#
#
# for i in range(n):
#     for j in range(n-1):
#         if data[j][3] > data[j+1][3]:
#             t = data[j]
#             data[j] = data[j+1]
#             data[j+1] = t
#
#         elif data[j][1] == data[j+1][1]:
#
#
# data.reverse()
#
# for j in range(n):
#     print(data[j][0], data[j][1], data[j][2])

# n = int(input())
#
# data = []
#
# for i in range(n):
#     x, y = map(int, input().split())
#     data.append([i+1, x, y])
#
# for i in range(n):
#     for j in range(n-1):
#         if data[j][1] < data[j+1][1]:
#             t = data[j]
#             data[j] = data[j+1]
#             data[j+1] = t
#
#         elif data[j][1] == data[j+1][1]:
#             if data[j][2] < data[j+1][2]:
#                 t = data[j]
#                 data[j] = data[j+1]
#                 data[j+1] = t
#
# for j in range(n):
#     print(data[j][0], data[j][1], data[j][2])




# [1, 100, 90, 100090]
# [2, 90, 100, 90100]
# [3, 80, 80, 80080]
# [4, 80, 90, 80090]
# [5, 60, 50, 60050]



# pre-processing    : sense
# processing        : Calculate
# post-processing

#1510
# n=int(input())
# a=(n-1)//2
# x=[]
#
# for i in range(n):
#     y=[0]*n
#     x.append(y)
#
#
# px = 0
# py = n//2
# k = 1
# x[px][py] = k
# k += 1
#
#
# for i in range(1, n**2):
#     px -= 1
#     py += 1
#
#     if px < 0:
#         px = n - 1
#     elif py >= n:
#         py = 0
#
#     x[px][py] = k
#     k += 1
#
#     if k > n*n:
#         break
#     if (k - 1) % n == 0:
#         px += 1
#         x[px][py] = k
#         k += 1
#         if k > n * n:
#             break
#
#
#
#
# for i in range(len(x)):
#     for j in range(len(x[i])):
#         print(x[i][j],sep=' ',end=' ')
#     print()

#1511
# n=int(input())
# x=[]
# for i in range(n):
#     y=[0]*n
#     x.append(y)
#
# p=0
# k=0
# for i in range(n):
#     for j in range(n):
#         p+=1
#         x[i][j]=p
#         if i==0 or i==n-1 or j==0 or j==n-1:
#             s=x[i][j]
#             k+=s
# print(k)

# for i in range(n):
#     for j in range(n):
#         s = x[0][j] + x[i][0] + x[i][n - 1] + x[n - 1][j]
#         print(x[i][j],sep=' ',end='')
#     print()

# function
# def books(name, outer, inner):
#     print('My Favarite book name is', name)
#     properties(outer, inner)
#
# def properties(outer, inner):
#     print('Book Outer color is', outer)
#     print('Book page is', inner)
#
# # method Overloading
# def summation(a, b):
#     return a+b
#
# def suv(a, b):
#     return a+b, a*b, a/b
#
# books('딥러닝 텐서플로 교과서', 'Red', 350)
# print(summation(10, 20))
# print(summation('Hello', 'World'))
#
# x, y, z = suv(10, 20)
# print(x, y, z)
#
# data = suv(10, 20)
# print(data[0])


# def calculate(a, b):
#     # 78 1201
#     year = a[:2]    # 78
#     month = a[2:4]
#     day = a[4:]
#
#     gender = 'M' if b[0] == '1' or b[0]=='3' else 'F'
#     if b[0] == '1' or b[0] == '2':
#         return '19'+year+'/'+month+'/'+day +' ' + gender
#     elif b[0] == '3' or b[0] == '4':
#         return '20'+year+'/'+month+'/'+day+' '+gender
#
# front, end = input().split('-')
# print(calculate(front, end))
#
# p=[]
# n=int(input())
#
# while True:
#     if (n % 2) >= 1:
#         p.append(n % 2)
#         n = n // 2
#     if (n%2) == 0 and n // 2 >= 2:
#         p.append(0)
#         n = n // 2
#     elif (n%2)==0 and n //2 < 2:
#         p.append(n//2)
#         break
# print(p)

#4013
# p = []
# 
# def convert():
#     while True:
#         p.append(n%2)
#         n = n//2
#         if n==0:
#             break
# 
#     while True:
#         print(p.pop(),end='')
#         if len(p) == 0:
#             break
# 
# n = int(input())


















90, 100090]# [2, 90, 100, 90100]# [3, 80, 80, 80080]# [4, 80, 90, 80090]# [5, 60, 50, 60050]# pre-processing    : sense# processing        : Calculate# post-processing#1510# n=int(input())# a=(n-1)//2# x=[]## for i in range(n):#     y=[0]*n#     x.append(y)### px = 0# py = n//2# k = 1# x[px][py] = k# k += 1### for i in range(1, n**2):#     px -= 1#     py += 1##     if px < 0:#         px = n - 1#     elif py >= n:#         py = 0##     x[px][py] = k#     k += 1##     if k > n*n:#         break#     if (k - 1) % n == 0:#         px += 1#         x[px][py] = k#         k += 1#         if k > n * n:#             break##### for i in range(len(x)):#     for j in range(len(x[i])):#         print(x[i][j],sep=' ',end=' ')#     print()#1511# n=int(input())# x=[]# for i in range(n):#     y=[0]*n#     x.append(y)## p=0# k=0# for i in range(n):#     for j in range(n):#         p+=1#         x[i][j]=p#         if i==0 or i==n-1 or j==0 or j==n-1:#             s=x[i][j]#             k+=s# print(k)# for i in range(n):#     for j in range(n):#         s = x[0][j] + x[i][0] + x[i][n - 1] + x[n - 1][j]#         print(x[i][j],sep=' ',end='')#     print()# function# def books(name, outer, inner):#     print('My Favarite book name is', name)#     properties(outer, inner)## def properties(outer, inner):#     print('Book Outer color is', outer)#     print('Book page is', inner)## # method Overloading# def summation(a, b):#     return a+b## def suv(a, b):#     return a+b, a*b, a/b## books('딥러닝 텐서플로 교과서', 'Red', 350)# print(summation(10, 20))# print(summation('Hello', 'World'))## x, y, z = suv(10, 20)# print(x, y, z)## data = suv(10, 20)# print(data[0])# def calculate(a, b):#     # 78 1201#     year = a[:2]    # 78#     month = a[2:4]#     day = a[4:]##     gender = 'M' if b[0] == '1' or b[0]=='3' else 'F'#     if b[0] == '1' or b[0] == '2':#         return '19'+year+'/'+month+'/'+day +' ' + gender#     elif b[0] == '3' or b[0] == '4':#         return '20'+year+'/'+month+'/'+day+' '+gender## front, end = input().split('-')# print(calculate(front, end))## p=[]# n=int(input())## while True:#     if (n % 2) >= 1:#         p.append(n % 2)#         n = n // 2#     if (n%2) == 0 and n // 2 >= 2:#         p.append(0)#         n = n // 2#     elif (n%2)==0 and n //2 < 2:#         p.append(n//2)#         break# print(p)#4013# p = []# # def convert():#     while True:#         p.append(n%2)#         n = n//2#         if n==0:#             break# #     while True:#         print(p.pop(),end='')#         if len(p) == 0:#             break# # n = int(input())