오늘한거
# a,b,c = map(int,input().split())
# v = 1
# while not (v%a==0 and v%b==0 and v%c==0) :
# v+=1
# print(v)
# import copy
#
# data = list(map(int,input().split()))
#
# a = copy.deepcopy(data)
#
# data.clear()
#
# print(a)
# for i in range(len(data)) :
# print(data[i])
# for x in data :
# print(x)
'''a = [1,3,4,7,4,5,1]
print(sum(a))
print(max(a))
print(min(a))
print(len(a))
a.sort()
print(a)
a.reverse()
print(a)
a.append(12)
print(a)
a.insert(2,100)
print(a)
a.pop()
print(a)
b = a.pop()
print(b)
print(a)
a.pop(3) #3번째 데이터 삭제
print(a)
a.append(4)
a.append(4)
print(a)
print(a.count(4))
print(a.index(50)) # 50의 위치 리턴
a.remove(7) #7값을 찾아서 삭제
a = int(input())
b = list(map(int,input().split()))
for i in range(1,24,1) :
print(b.count(i),end=' ')'''
# a = int(input())
# b = list(map(int,input().split()))
# b.reverse()
# for i in range(0,len(b),1) :
# print(b[i],end=' ')
# a = int(input())
# b = list(map(int,input().split()))
# print(min(b))
# a = int(input())
# for i in range(5):
#
# a = [ [0 for i in range(10)] for j in range(10) ]
# print(a)
# 가로 w, 세로 h인 이차원 배열 만들기
# a = []
# w, h = 10,10
# for i in range(h) :
# a.append(list(map(int,input().split())))
# # a.append([0]*w)
#
# print(a)
# a[0][0] = 10
#
# print(a)
# a = [[0 for i in range(20)] for j in range(20)]
# b = int(input())
# for i in range(b) :
# c = list(map(int,input().split()))
# a[c[0]][c[1]] = 1
# for i in range(1,20):
# for j in range(1,20):
# print(a[i][j],end='')
# if j!=19 :
# print(' ',end='')
# if(i==19):
# print('',end='')
# else:
# print('')
# a = []
# w,h = 20,20
# for i in range(0,19):
# a.append(list(map(int,input().split())))
# x = int(input())
# for i in range(x):
# c = list(map(int,input().split()))
# for j in range(0,19):
# if not j==c[0]-1:
# a[j][c[1]-1] = int(not a[j][c[1]-1])
# if not j==c[1]-1:
# a[c[0]-1][j] = int(not a[c[0]-1][j])
# for i in range(0,19):
# for j in range(0,19):
# print(a[i][j],end='')
# if j!=18:
# print(' ',end='')
# if i != 18:
# print('')
# y,x = map(int,input().split())
# a = [[0 for i in range(x)] for j in range(y)]
# c = int(input())
# for i in range(c):
# v = list(map(int,input().split()))
# v[3] -= 1
# v[2] -= 1
# for j in range(v[0]):
# if v[1]==0:
# #if j + v[3] > x-1:
# # break
# a[v[2]][j + v[3]] = 1
# else :
# #if j + v[2] > y-1:
# # break
# a[j + v[2]][v[3]] = 1
# for i in range(y):
# for j in range(x):
# print(a[i][j],end = '')
# if j != x-1:
# print(' ',end='')
# if i != y-1:
# print('')
# a = []
# for i in range(10):
# a.append(list(map(int,input().split())))
# x = 1
# y = 1
# while 1 :
# if a[y][x]==2 :
# a[y][x]=9
# break
# a[y][x] = 9
# if a[y][x+1]!=1:
# x += 1
# elif a[y][x+1]==1 and a[y+1][x]!=1:
# y+=1
# else :
# break
# for i in range(10):
# for j in range(10):
# print(a[i][j],end='')
# if j!=9:
# print(' ',end='')
# if i != 9:
# print('')
# # 이차원배열 정렬
# a = [ [1,3] , [3,2] , [2,7] ]
# a.sort(key = lambda x : -x[1])
# print(a)
#
# a = []
# 1805
# 3015
# 3019
# 3108
# a = int(input())
# b= []
# for i in range(a):
# b.append(list(map(int,input().split())))
# b.sort(key= lambda x : x[0])
# for i in range(a):
# print(b[i][0],b[i][1])
# a,b = map(int,input().split())
# c = []
# for i in range(a):
# c.append(list(input().split()))
# c[i][1] = int(c[i][1])
# c.sort(key= lambda x : -x[1])
# for i in range(b):
# print(c[i][0])
# a = list(map(int,input('').split()))
# print(a)
# a = list(input())
# print(a)
# a = list(map(int, a))
# print(a)
# 스택 stack : 쌓는거, 나중에들어온게 먼저나가는 구조, 후입선출 -> Last In First Out -> LIFO
# st = []
#
# st.append("hello")
# st.pop()
# top -> len(st)-1
# stack의 구조 활용 문제
# 1. 3117 2016 3102 -> 스택연습
# 2. 3127 3130 -> 리얼 스택 활용
# a = []
# c = 0
# x = int(input())
# for i in range(x):
# n = int(input())
# if n!=0:
# a.append(n)
# else:
# a.pop()
# for i in range(len(a)):
# c += a[i]
# print(c)
# a = int(input())
# x = list(map(int,input()))
# c = []
# x.reverse()
# for i in range(len(x)):
# c.append(x[i])
# if (i+1)%3==0 and i!= len(x)-1:
# c.append(',')
# c.reverse()
# for i in range(len(c)):
# print(c[i],end='')
# a = int(input())
# sk = []
# for i in range(a):
# x = input()
# if x == 'top()':
# if len(sk)==0:
# print(-1)
# continue
# print(sk[len(sk)-1])
# elif x =='pop()' and len(sk) != 0:
# sk.pop()
# elif x == 'size()':
# print(len(sk))
# elif x == 'empty()' :
# print('true' if len(sk)==0 else 'false')
# elif x[1] =='u' :
# sk.append(int(x[6:-2]))
# #print(int(x[6:-2]))
# a = list(input().split())
# jsby = []
# def ys(x):
# jsby.pop()
# jsby.pop()
# jsby.append(x)
#
# for i in range(len(a)):
# if a[i]=='+':
# x = jsby[-1] + jsby[-2]
# ys(x)
# elif a[i]=='-':
# x = jsby[-2] - jsby[-1]
# ys(x)
# elif a[i]=='*':
# x = jsby[-1] * jsby[-2]
# ys(x)
# else:
# jsby.append(int(a[i]))
# # print(jsby[-1])
# print(jsby[0])2회 조회