231105

# x = input()

# a = 0

# b = 0

# for i in range(len(x)):

# if x[i] == '(':

# a += 1

# elif x[i] == ')':

# b += 1

# print(a, b)

# x = int(input())

# # data = list(map(int, input()))

# data = []

# for i in range(x-1):

# v = int(input())

# data.append(v)

# data.sort()

# for i in range(1, x+1):

# if data[i-1] != i:

# print(i)

# break

# x = int(input())

# data = []

# for i in range(x-1):

# y = int(input())

# data.append(y)

# data.sort()

# data.append(9999999999999)

# for i in range(1, x+1):

# if data[i-1] != i:

# print(i)

# break

# x = int(input())

# s = 0

#

# for i in range(1, x+1):

# s += i

# print(s)

#

# for i in range(x-1):

# v = int(input())

# s -= v

# print(s)

# x = int(input())

# data = [0] * (x+1) # 0 ~ 10

# for i in range(x-1):

# v = int(input())

# data[v] = 1

# print(data)

#

# for i in range(1, x+1):

# if data[i] == 0:

# print(i)

# x = input()

# v = [0] * 26 # 0 ~ 25

# for i in range(len(x)):

# if x[i] >= 'a' and x[i] <= 'z': # a = 97, z = 123

# p = ord(x[i]) - ord('a')

# v[p] = v[p] + 1

# print(v)

# x, y = input().split('-')

#

# if y[0] == '1':

# print("19", x[0],x[1], "/", x[2],x[3], "/", x[4],x[5], " M", sep='')

# elif y[0] == '2':

# print("19", x[0],x[1], "/", x[2],x[3], "/", x[4],x[5], " F", sep='')

# elif y[0] == '3':

# print("20", x[0], x[1], "/", x[2], x[3], "/", x[4],x[5], " M", sep='')

# elif y[0] == '4':

# print("20", x[0], x[1], "/", x[2], x[3], "/", x[4],x[5], " F", sep='')

# id = input()

# print(id[0:2]) # start - (end-1)

#

# x = int(input())

# a = []

# b = 0

# c = 0

#

# tx = x

#

# for i in range(10000):

# a.append(tx % 2)

# tx = tx // 2

# if tx == 0:

# break

#

# for i in range(len(a)-1, -1, -1):

# print(a[i], end='')

# for i in range(x-1):

# if i[x-1] % 2 == 0 or i[x-1] % 2 == 1:

# a = [x-1] % 2

# print('2', a)

# elif i[x-1] % 8 == 0 or 1 or 2 or 3 or 4 or 5 or 6 or 7:

# b = [x-1] % 8

# print('8', b)

# elif i[x-1] % 16 == 10 or 11 or 12 or 13 or 14 or 15:

# c = [x-1] % 16

# print('16', c)

#-------------------------------------------------------

# data = list(map(int, input().split()))

# a = 0

# for i in range(len(data)):

# if data[i] % 2 != 0:

# a += data[i]

# if a == 0:

# print("-1")

# else:

# print(a)

#-----------------------------------------------------

# data = list(map(int, input().split()))

# a = 0

# for i in range(len(data)):

# if data[i] % 2 != 0:

# a += data[i]

# if a == 0:

# print("-1")

# else:

# print(a)

# x, y, z = map(int, input().split())

# p = 0

# for i in range(1, z+1):

# if x % i == 0 and y % i ==0 and z % i== 0:

# p = i

# print(p)

#-------------------------------------------------------

# a = 0

# m = 101

#

# for i in range(7):

# v = int(input())

# if v % 2 != 0:

# a += v

# if m > v:

# m = v

# if a != 0:

# print(a)

# print(m)

# else:

# print("-1")

# data = list(map(int, input().split()))

# data.sort()

# print(data[2])

# data = list(map(int, input().split()))

# data.sort()

# a = 0

# b = 0

# for i in range(len(data)):

# if data[i] % 2 != 0:

# if a < data[i]:

# a = data[i]

# if data[i] % 2 == 0:

# if b < data[i]:

# b = data[i]

# print(a+b)

# x, y = input().split('-')

#

# if y[0] == '1':

# print('19', x[0:2], '/', x[2:4], '/', x[4:6], ' M', sep='')

# elif y[0] == '2':

# print('19', x[0:2], '/', x[2:4], '/', x[4:6], ' F', sep='')

# elif y[0] == '3':

# print('20', x[0:2], '/', x[2:4], '/', x[4:6], ' M', sep='')

# elif y[0] == '4':

# print('20', x[0:2], '/', x[2:4], '/', x[4:6], ' F', sep='')

# x, y, z = input().split()

# x = int(x)

# y = int(y)

# z = int(z)

# a=0

# for i in range(1, z+1):

# if z % i == 0 and y % i == 0 and x % i == 0:

# a = i

# print(a)

# data = list(map(int, input().split()))

# a = 0

# for i in range(len(data)):

# if data[i] % 2 != 0:

# a += data[i]

# if a == 0:

# print('-1')

# else:

# print(a)

# data = list(map(int, input().split()))

# data.sort()

# print(data[2])

# a = 0

# b = 101

# for i in range(7):

# v = int(input())

# if v % 2 != 0:

# a += v

# if v < b:

# b = v

# print(a)

# print(b)

'''

60:> 2~59(1, 60)

61:> 2~60(1, 61)

'''

# def prime(k):

# for i in range(2, k):

# if k % i == 0:

# return False

# return True

#

# m, n = map(int, input().split())

# a = 0

# b = 0

#

# for i in range(m, n+1):

# if prime(i):

# print(i)

# n, k = map(int, input().split())

# a = []

# for i in range(1,n+1):

# if n % i == 0:

# a.append(i)

#

# print(a[k-1])

#

# n, k = map(int, input().split())

#

# def divisor( n, k ):

# a = []

# for i in range(1, n+1):

# if n % i == 0:

# a.append(i)

# return a[k-1]

#

# print(divisor(n, k))

# x, y, z = map(int, input().split())

# a = input()

# a = int(a)

# k = x*3600 + y*60 + z + a

# k = int(k)

# print(k//3600 % 24, (k % 3600)//60, (k % 3600) % 60)

# x = [0, 0, 0, 0, 0] # 1d list

#

# x = [ # 2d list

# [0, 0, 0, 0, 0],

# [0, 0, 0, 0, 0],

# [0, 0, 0, 0, 0],

# [0, 0, 0, 0, 0],

# [0, 0, 0, 0, 0]

# ]

# x = [0] * 5

# print(x)

#

# Input Data(SIZE)

# n = int(input())

#

# Init: List(2D)

# data = []

# for i in range(n):

# y = [0] * n # list

# data.append(y)

#

# print(data)

#

# Edit Data:

# data[3][3] = 9

#

# view simple

# print(data)

#

# designed

# for i in range(n):

# for j in range(n):

# print(data[i][j], end=' ')

# print()

# n = int(input())

#

# data = []

# for i in range(n):

# x = [0] * n

# data.append(x)

#

# k = 1

#

# for i in range(n):

# for j in range(n):

# data[i][j] = k

# k += 1

#

# for i in range(n):

# for j in range(n):

# print(data[i][j], end=' ')

# print()

#

# n = int(input())

# data = []

# for i in range(n):

# x = [0]*n

# data.append(x)

#

# k = 1

# for i in range(n):

# for j in range(n-1, -1, -1):

# data[i][j] = k

# k += 1

#

# for i in range(n):

# for j in range(n):

# print(data[i][j], end=' ')

# print()

# n = int(input())

# data = []

# for i in range(n):

# x = [0] * n

# data.append(x)

#

# k = 1

# for i in range(n):

# for j in range(n):

# data[i][j] = k

# k += 1

#

# for i in range(n):

# for j in range(n):

# print(data[j][i], end=' ')

# print()

# n = int(input())

# data =[]

# for i in range(n):

# x = [0] * n

# data.append(x)

# k = 1

# for i in range(n):

# for j in range(n):

# data[i][j] = k

# k += 1

#

# for i in range(n-1, -1, -1):

# for j in range(n):

# print(data[j][i], end=' ')

# print()

# n, m = map(int, input().split())

# data = []

# for i in range(n):

# x = [0] * n

# for j in range(m):

# x = [0] * m

# data.append(x)

#

# k = 1

# for i in range(n):

# for j in range(m):

# data[i][j] = k

# k += 1

#

# for i in range(n-1, -1, -1):

# for j in range(m-1, -1, -1):

# print(data[i][j], end=' ')

# print()

# n, m = map(int, input().split())

# data = []

# for i in range(n):

# x = [0] * n

# for j in range(m):

# x = [0] * m

# data.append(x)

# k = 1

# for i in range(n):

# for j in range(m):

# data[i][j] = k

# k += 1

#

# for i in range(n-1, -1, -1):

# for j in range(m):

# print(data[i][j], end=' ')

# print()

# n, m = map(int, input().split())

# data = []

# for i in range(n):

# x = [0]*n

# for j in range(m):

# x = [0]*m

# data.append(x)

# k = 1

# for j in range(m-1, -1, -1):

# for i in range(n-1, -1, -1):

# data[i][j] = k

# k += 1

# for i in range(n):

# for j in range(m):

# print(data[i][j], end=' ')

# print()

# n, m = map(int, input().split())

# data = []

# for i in range(n):

# x = [0] * n

# for j in range(m):

# x = [0] * m

# data.append(x)

# k = 1

# for j in range(m-1, -1, -1):

# for i in range(n):

# data[i][j] = k

# k += 1

# for i in range(n):

# for j in range(m):

# print(data[i][j], end=' ')

# print()

# n = int(input())

# data = []

#

# for i in range(19):

# x = [0] * 19

# data.append(x)

#

# for i in range(n):

# x, y = map(int, input().split())

# data[x-1][y-1] = 1

#

# for i in range(19):

# for j in range(19):

# print(data[i][j], end=' ')

# print()

# data=[]

# for i in range(19):

# v = list(map(int, input().split()))

# x = [0]*19

# data.append(v)

# n = int(input())

#

# for i in range(n):

# m, k = map(int, input().split())

# m -= 1

# k -= 1

# for j in range(19):

# if data[m][j] == 1:

# data[m][j] = 0

# else:

# data[m][j] = 1

# for j in range(19):

# if data[j][k] == 1:

# data[j][k] = 0

# else:

# data[j][k] = 1

#

# for i in range(19):

# for j in range(19):

# print(data[i][j], end=' ')

# print()