# for i in range(100):
# print(i+1, end=' ')
# n = input()
# n = int(n)
# for i in range(n):
# print(i+1, end=' ')
# a, b=map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# for i in range(a,b+1,1):
# print(i, end=' ')
# a, b=input().split()
# a = ord(a)
# b = ord(b)
# for i in range(a,b+1,1):
# print(chr(i), end=' ')
# a, b = map(int, input().split())
# if a%2 == 0:
# a = a+1
# if b%2 == 0:
# b = b-1
# for i in range(a,b+1,2):
# print(i, end=' ')
# n = input()
# n = int(n)
# s = 0
# for i in range(1, n+1, 1):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# if n%2 == 1:
# n = n-1
# s = 0
# for i in range(2, n+1, 2):
# s = s+i
# print(s)
# a, b = map(int, input().split())
# if a%3 == 1:
# a = a+2
# elif a%3 == 2:
# a = a+1
# s = 0
# for i in range(a,b+1,3):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%5 == 0:
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%2 == 1:
# s = s+1
# print(s)
# a, b = map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# s = 0
# if a%2 == 1:
# print(a, end='')
# s = s+a
# else:
# print(-a, end='')
# s = s-a
# for i in range(a+1, b+1, 1):
# if i%2 == 1:
# print('+',i, sep='', end='')
# s = s+i
# else:
# print(-i, end='')
# s = s-i
# print('=', s, sep='')
'''
list : []
- 변형, 삽입, 삭제, 정렬, 등 모두 가능
- [10, 20, [30, 40,], 50]
tuple : ()
- 변형안됨
dictionary : {}
- key:value
- 단어:뜻
dict123123['apple'] = 100
'''
# dic = {}
# dic['apple'] = 100
# dic['banana'] = 200
# dic['apple'] = 300
#
# print(dic.keys())
# data = []
# data.append(10)
# data.append(20)
# data.append(30)
# data.append(40)
#
# print(data)
#
# data.pop()
# print(data)
#
# data.pop(0)
# print(data)
#
# data.append(10)
# data.append(20)
# data.append(30)
#
# print(data)
#
# data.sort()
#
# print(data)
#
# data.sort(reverse=True)
# print(data)
#
# data.remove(10)
# print(data)
#
# data.insert(4, 2)
# print(data)
# x = data.index(2)
# print(x)
#
# p = data.copy()
#
# print(p, data)
#
# p.append(100)
#
# print(p, data)
#
# k = data
#
# print(k, data)
#
# k.append(200)
# print(k, data)
# data = list(input())
# k = [0] * 26
# for i in range(len(data)):
# if 123 > ord(data[i]) > 96:
# t = ord(data[i])
# k[t-97] = k[t-97]+1
# for i in range(0, 26, 1):
# print(chr(i+97), ':', k[i], sep='')
# n = input()
# n = int(n)
# for i in range(n//2+1):
# for j in range((n-1-2*i)//2):
# print(' ',end='')
# for j in range(2*i+1):
# print('*',end='')
# print()
# n, k = map(int, input().split())
# for i in range(n):
# if i == 0 or i == n-1:
# for j in range(n):
# print('*', end='')
# print()
# else:
# print('*', end='')
# for j in range(n-2):
# if (k-i-2)%k == j%k:
# print('*',end='')
# else:
# print(' ', end='')
# print('*')
# n, k = map(int, input().split())
#
# for i in range(n):
# for j in range(n):
# if i == 0 or j == 0 or i ==n-1 or j==n-1 or (i+j+1)%k==0:
# print('*', end='')
# else:
# print(' ' , end='')
# print()
# n = int(input())
# data = list(input().split())
# for i in range(n):
# for j in range(n):
# t = (i + j) % n
# print(data[t], end=' ')
# print()
# n = int(input())
# d = [0] * 3
# k = []
# for i in range(n):
# a, b = input().split()
# b = int(b)
# if b > d[0]:
# d.insert(0, b)
# k.insert(0, a)
# elif b > d[1]:
# d.insert(1, b)
# k.insert(1, a)
# elif b > d[2]:
# d.insert(2, b)
# k.insert(2, a)
# print(k[2])
# n = int(input())
# d = list(map(int, input().split()))
# for i in range(n):
# print(i+1, ':', sep='', end=' ')
# for j in range(n):
# if i == j:
# continue
# if d[i] < d[j]:
# print('<', end=' ')
# elif d[i] == d[j]:
# print('=', end=' ')
# else:
# print('>', end=' ')
# print()
# d = []
# for i in range(19):
# v = [0] * 19
# v = list(map(int, input().split()))
# d.append(v)
#
# n = int(input())
# for i in range(n):
# x, y = input().split()
# for j in range(19):
# if d[j][int(y)-1] == 0:
# d[j][int(y)-1] = 1
# else:
# d[j][int(y)-1] = 0
#
# if d[int(x)-1][j] == 0:
# d[int(x)-1][j] = 1
# else:
# d[int(x)-1][j] = 0
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# h, w = map(int, input().split())
# n = int(input())
# da = []
# for i in range(h):
# v = [0] * w
# da.append(v)
# for i in range(n):
# l, d, x, y = map(int, input().split())
# if d == 0:
# for j in range(l):
# da[x-1][y-1+j] = 1
# else:
# for j in range(l):
# da[x-1+j][y-1] = 1
#
# for i in range(len(da)):
# for j in range(len(da[i])):
# print(da[i][j], end=' ')
# print()
# d = []
# for i in range(10):
# v = [0] * 10
# v = list(map(int, input().split()))
# d.append(v)
#
# x = 1
# y = 1
# if d[x][y] == 2:
# d[1][1] = 9
# else:
# d[1][1] = 9
# while(d[x][y] == 9):
# if d[x][y+1] == 2:
# d[x][y+1] = 9
# break
# elif d[x][y+1] == 0:
# d[x][y+1] = 9
# y = y+1
# else:
# if d[x+1][y] == 2:
# d[x+1][y] = 9
# x = x+1
# break
# elif d[x+1][y] == 0:
# d[x+1][y] = 9
# x = x+1
# else:
# break
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# for i in range(100):
# print(i+1, end=' ')
# n = input()
# n = int(n)
# for i in range(n):
# print(i+1, end=' ')
# a, b=map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# for i in range(a,b+1,1):
# print(i, end=' ')
# a, b=input().split()
# a = ord(a)
# b = ord(b)
# for i in range(a,b+1,1):
# print(chr(i), end=' ')
# a, b = map(int, input().split())
# if a%2 == 0:
# a = a+1
# if b%2 == 0:
# b = b-1
# for i in range(a,b+1,2):
# print(i, end=' ')
# n = input()
# n = int(n)
# s = 0
# for i in range(1, n+1, 1):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# if n%2 == 1:
# n = n-1
# s = 0
# for i in range(2, n+1, 2):
# s = s+i
# print(s)
# a, b = map(int, input().split())
# if a%3 == 1:
# a = a+2
# elif a%3 == 2:
# a = a+1
# s = 0
# for i in range(a,b+1,3):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%5 == 0:
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%2 == 1:
# s = s+1
# print(s)
# a, b = map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# s = 0
# if a%2 == 1:
# print(a, end='')
# s = s+a
# else:
# print(-a, end='')
# s = s-a
# for i in range(a+1, b+1, 1):
# if i%2 == 1:
# print('+',i, sep='', end='')
# s = s+i
# else:
# print(-i, end='')
# s = s-i
# print('=', s, sep='')
'''
list : []
- 변형, 삽입, 삭제, 정렬, 등 모두 가능
- [10, 20, [30, 40,], 50]
tuple : ()
- 변형안됨
dictionary : {}
- key:value
- 단어:뜻
dict123123['apple'] = 100
'''
# dic = {}
# dic['apple'] = 100
# dic['banana'] = 200
# dic['apple'] = 300
#
# print(dic.keys())
# data = []
# data.append(10)
# data.append(20)
# data.append(30)
# data.append(40)
#
# print(data)
#
# data.pop()
# print(data)
#
# data.pop(0)
# print(data)
#
# data.append(10)
# data.append(20)
# data.append(30)
#
# print(data)
#
# data.sort()
#
# print(data)
#
# data.sort(reverse=True)
# print(data)
#
# data.remove(10)
# print(data)
#
# data.insert(4, 2)
# print(data)
# x = data.index(2)
# print(x)
#
# p = data.copy()
#
# print(p, data)
#
# p.append(100)
#
# print(p, data)
#
# k = data
#
# print(k, data)
#
# k.append(200)
# print(k, data)
# data = list(input())
# k = [0] * 26
# for i in range(len(data)):
# if 123 > ord(data[i]) > 96:
# t = ord(data[i])
# k[t-97] = k[t-97]+1
# for i in range(0, 26, 1):
# print(chr(i+97), ':', k[i], sep='')
# n = input()
# n = int(n)
# for i in range(n//2+1):
# for j in range((n-1-2*i)//2):
# print(' ',end='')
# for j in range(2*i+1):
# print('*',end='')
# print()
# n, k = map(int, input().split())
# for i in range(n):
# if i == 0 or i == n-1:
# for j in range(n):
# print('*', end='')
# print()
# else:
# print('*', end='')
# for j in range(n-2):
# if (k-i-2)%k == j%k:
# print('*',end='')
# else:
# print(' ', end='')
# print('*')
# n, k = map(int, input().split())
#
# for i in range(n):
# for j in range(n):
# if i == 0 or j == 0 or i ==n-1 or j==n-1 or (i+j+1)%k==0:
# print('*', end='')
# else:
# print(' ' , end='')
# print()
# n = int(input())
# data = list(input().split())
# for i in range(n):
# for j in range(n):
# t = (i + j) % n
# print(data[t], end=' ')
# print()
# n = int(input())
# d = [0] * 3
# k = []
# for i in range(n):
# a, b = input().split()
# b = int(b)
# if b > d[0]:
# d.insert(0, b)
# k.insert(0, a)
# elif b > d[1]:
# d.insert(1, b)
# k.insert(1, a)
# elif b > d[2]:
# d.insert(2, b)
# k.insert(2, a)
# print(k[2])
# n = int(input())
# d = list(map(int, input().split()))
# for i in range(n):
# print(i+1, ':', sep='', end=' ')
# for j in range(n):
# if i == j:
# continue
# if d[i] < d[j]:
# print('<', end=' ')
# elif d[i] == d[j]:
# print('=', end=' ')
# else:
# print('>', end=' ')
# print()
# d = []
# for i in range(19):
# v = [0] * 19
# v = list(map(int, input().split()))
# d.append(v)
#
# n = int(input())
# for i in range(n):
# x, y = input().split()
# for j in range(19):
# if d[j][int(y)-1] == 0:
# d[j][int(y)-1] = 1
# else:
# d[j][int(y)-1] = 0
#
# if d[int(x)-1][j] == 0:
# d[int(x)-1][j] = 1
# else:
# d[int(x)-1][j] = 0
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# h, w = map(int, input().split())
# n = int(input())
# da = []
# for i in range(h):
# v = [0] * w
# da.append(v)
# for i in range(n):
# l, d, x, y = map(int, input().split())
# if d == 0:
# for j in range(l):
# da[x-1][y-1+j] = 1
# else:
# for j in range(l):
# da[x-1+j][y-1] = 1
#
# for i in range(len(da)):
# for j in range(len(da[i])):
# print(da[i][j], end=' ')
# print()
# d = []
# for i in range(10):
# v = [0] * 10
# v = list(map(int, input().split()))
# d.append(v)
#
# x = 1
# y = 1
# if d[x][y] == 2:
# d[1][1] = 9
# else:
# d[1][1] = 9
# while(d[x][y] == 9):
# if d[x][y+1] == 2:
# d[x][y+1] = 9
# break
# elif d[x][y+1] == 0:
# d[x][y+1] = 9
# y = y+1
# else:
# if d[x+1][y] == 2:
# d[x+1][y] = 9
# x = x+1
# break
# elif d[x+1][y] == 0:
# d[x+1][y] = 9
# x = x+1
# else:
# break
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# for i in range(100):
# print(i+1, end=' ')
# n = input()
# n = int(n)
# for i in range(n):
# print(i+1, end=' ')
# a, b=map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# for i in range(a,b+1,1):
# print(i, end=' ')
# a, b=input().split()
# a = ord(a)
# b = ord(b)
# for i in range(a,b+1,1):
# print(chr(i), end=' ')
# a, b = map(int, input().split())
# if a%2 == 0:
# a = a+1
# if b%2 == 0:
# b = b-1
# for i in range(a,b+1,2):
# print(i, end=' ')
# n = input()
# n = int(n)
# s = 0
# for i in range(1, n+1, 1):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# if n%2 == 1:
# n = n-1
# s = 0
# for i in range(2, n+1, 2):
# s = s+i
# print(s)
# a, b = map(int, input().split())
# if a%3 == 1:
# a = a+2
# elif a%3 == 2:
# a = a+1
# s = 0
# for i in range(a,b+1,3):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%5 == 0:
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%2 == 1:
# s = s+1
# print(s)
# a, b = map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# s = 0
# if a%2 == 1:
# print(a, end='')
# s = s+a
# else:
# print(-a, end='')
# s = s-a
# for i in range(a+1, b+1, 1):
# if i%2 == 1:
# print('+',i, sep='', end='')
# s = s+i
# else:
# print(-i, end='')
# s = s-i
# print('=', s, sep='')
'''
list : []
- 변형, 삽입, 삭제, 정렬, 등 모두 가능
- [10, 20, [30, 40,], 50]
tuple : ()
- 변형안됨
dictionary : {}
- key:value
- 단어:뜻
dict123123['apple'] = 100
'''
# dic = {}
# dic['apple'] = 100
# dic['banana'] = 200
# dic['apple'] = 300
#
# print(dic.keys())
# data = []
# data.append(10)
# data.append(20)
# data.append(30)
# data.append(40)
#
# print(data)
#
# data.pop()
# print(data)
#
# data.pop(0)
# print(data)
#
# data.append(10)
# data.append(20)
# data.append(30)
#
# print(data)
#
# data.sort()
#
# print(data)
#
# data.sort(reverse=True)
# print(data)
#
# data.remove(10)
# print(data)
#
# data.insert(4, 2)
# print(data)
# x = data.index(2)
# print(x)
#
# p = data.copy()
#
# print(p, data)
#
# p.append(100)
#
# print(p, data)
#
# k = data
#
# print(k, data)
#
# k.append(200)
# print(k, data)
# data = list(input())
# k = [0] * 26
# for i in range(len(data)):
# if 123 > ord(data[i]) > 96:
# t = ord(data[i])
# k[t-97] = k[t-97]+1
# for i in range(0, 26, 1):
# print(chr(i+97), ':', k[i], sep='')
# n = input()
# n = int(n)
# for i in range(n//2+1):
# for j in range((n-1-2*i)//2):
# print(' ',end='')
# for j in range(2*i+1):
# print('*',end='')
# print()
# n, k = map(int, input().split())
# for i in range(n):
# if i == 0 or i == n-1:
# for j in range(n):
# print('*', end='')
# print()
# else:
# print('*', end='')
# for j in range(n-2):
# if (k-i-2)%k == j%k:
# print('*',end='')
# else:
# print(' ', end='')
# print('*')
# n, k = map(int, input().split())
#
# for i in range(n):
# for j in range(n):
# if i == 0 or j == 0 or i ==n-1 or j==n-1 or (i+j+1)%k==0:
# print('*', end='')
# else:
# print(' ' , end='')
# print()
# n = int(input())
# data = list(input().split())
# for i in range(n):
# for j in range(n):
# t = (i + j) % n
# print(data[t], end=' ')
# print()
# n = int(input())
# d = [0] * 3
# k = []
# for i in range(n):
# a, b = input().split()
# b = int(b)
# if b > d[0]:
# d.insert(0, b)
# k.insert(0, a)
# elif b > d[1]:
# d.insert(1, b)
# k.insert(1, a)
# elif b > d[2]:
# d.insert(2, b)
# k.insert(2, a)
# print(k[2])
# n = int(input())
# d = list(map(int, input().split()))
# for i in range(n):
# print(i+1, ':', sep='', end=' ')
# for j in range(n):
# if i == j:
# continue
# if d[i] < d[j]:
# print('<', end=' ')
# elif d[i] == d[j]:
# print('=', end=' ')
# else:
# print('>', end=' ')
# print()
# d = []
# for i in range(19):
# v = [0] * 19
# v = list(map(int, input().split()))
# d.append(v)
#
# n = int(input())
# for i in range(n):
# x, y = input().split()
# for j in range(19):
# if d[j][int(y)-1] == 0:
# d[j][int(y)-1] = 1
# else:
# d[j][int(y)-1] = 0
#
# if d[int(x)-1][j] == 0:
# d[int(x)-1][j] = 1
# else:
# d[int(x)-1][j] = 0
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# h, w = map(int, input().split())
# n = int(input())
# da = []
# for i in range(h):
# v = [0] * w
# da.append(v)
# for i in range(n):
# l, d, x, y = map(int, input().split())
# if d == 0:
# for j in range(l):
# da[x-1][y-1+j] = 1
# else:
# for j in range(l):
# da[x-1+j][y-1] = 1
#
# for i in range(len(da)):
# for j in range(len(da[i])):
# print(da[i][j], end=' ')
# print()
# d = []
# for i in range(10):
# v = [0] * 10
# v = list(map(int, input().split()))
# d.append(v)
#
# x = 1
# y = 1
# if d[x][y] == 2:
# d[1][1] = 9
# else:
# d[1][1] = 9
# while(d[x][y] == 9):
# if d[x][y+1] == 2:
# d[x][y+1] = 9
# break
# elif d[x][y+1] == 0:
# d[x][y+1] = 9
# y = y+1
# else:
# if d[x+1][y] == 2:
# d[x+1][y] = 9
# x = x+1
# break
# elif d[x+1][y] == 0:
# d[x+1][y] = 9
# x = x+1
# else:
# break
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# for i in range(100):
# print(i+1, end=' ')
# n = input()
# n = int(n)
# for i in range(n):
# print(i+1, end=' ')
# a, b=map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# for i in range(a,b+1,1):
# print(i, end=' ')
# a, b=input().split()
# a = ord(a)
# b = ord(b)
# for i in range(a,b+1,1):
# print(chr(i), end=' ')
# a, b = map(int, input().split())
# if a%2 == 0:
# a = a+1
# if b%2 == 0:
# b = b-1
# for i in range(a,b+1,2):
# print(i, end=' ')
# n = input()
# n = int(n)
# s = 0
# for i in range(1, n+1, 1):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# if n%2 == 1:
# n = n-1
# s = 0
# for i in range(2, n+1, 2):
# s = s+i
# print(s)
# a, b = map(int, input().split())
# if a%3 == 1:
# a = a+2
# elif a%3 == 2:
# a = a+1
# s = 0
# for i in range(a,b+1,3):
# s = s+i
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%5 == 0:
# s = s+data[i]
# print(s)
# n = input()
# n = int(n)
# data = list(map(int, input().split()))
# s = 0
# for i in range(n):
# if data[i]%2 == 1:
# s = s+1
# print(s)
# a, b = map(int, input().split())
# if a > b:
# t = a
# a = b
# b = t
# s = 0
# if a%2 == 1:
# print(a, end='')
# s = s+a
# else:
# print(-a, end='')
# s = s-a
# for i in range(a+1, b+1, 1):
# if i%2 == 1:
# print('+',i, sep='', end='')
# s = s+i
# else:
# print(-i, end='')
# s = s-i
# print('=', s, sep='')
'''
list : []
- 변형, 삽입, 삭제, 정렬, 등 모두 가능
- [10, 20, [30, 40,], 50]
tuple : ()
- 변형안됨
dictionary : {}
- key:value
- 단어:뜻
dict123123['apple'] = 100
'''
# dic = {}
# dic['apple'] = 100
# dic['banana'] = 200
# dic['apple'] = 300
#
# print(dic.keys())
# data = []
# data.append(10)
# data.append(20)
# data.append(30)
# data.append(40)
#
# print(data)
#
# data.pop()
# print(data)
#
# data.pop(0)
# print(data)
#
# data.append(10)
# data.append(20)
# data.append(30)
#
# print(data)
#
# data.sort()
#
# print(data)
#
# data.sort(reverse=True)
# print(data)
#
# data.remove(10)
# print(data)
#
# data.insert(4, 2)
# print(data)
# x = data.index(2)
# print(x)
#
# p = data.copy()
#
# print(p, data)
#
# p.append(100)
#
# print(p, data)
#
# k = data
#
# print(k, data)
#
# k.append(200)
# print(k, data)
# data = list(input())
# k = [0] * 26
# for i in range(len(data)):
# if 123 > ord(data[i]) > 96:
# t = ord(data[i])
# k[t-97] = k[t-97]+1
# for i in range(0, 26, 1):
# print(chr(i+97), ':', k[i], sep='')
# n = input()
# n = int(n)
# for i in range(n//2+1):
# for j in range((n-1-2*i)//2):
# print(' ',end='')
# for j in range(2*i+1):
# print('*',end='')
# print()
# n, k = map(int, input().split())
# for i in range(n):
# if i == 0 or i == n-1:
# for j in range(n):
# print('*', end='')
# print()
# else:
# print('*', end='')
# for j in range(n-2):
# if (k-i-2)%k == j%k:
# print('*',end='')
# else:
# print(' ', end='')
# print('*')
# n, k = map(int, input().split())
#
# for i in range(n):
# for j in range(n):
# if i == 0 or j == 0 or i ==n-1 or j==n-1 or (i+j+1)%k==0:
# print('*', end='')
# else:
# print(' ' , end='')
# print()
# n = int(input())
# data = list(input().split())
# for i in range(n):
# for j in range(n):
# t = (i + j) % n
# print(data[t], end=' ')
# print()
# n = int(input())
# d = [0] * 3
# k = []
# for i in range(n):
# a, b = input().split()
# b = int(b)
# if b > d[0]:
# d.insert(0, b)
# k.insert(0, a)
# elif b > d[1]:
# d.insert(1, b)
# k.insert(1, a)
# elif b > d[2]:
# d.insert(2, b)
# k.insert(2, a)
# print(k[2])
# n = int(input())
# d = list(map(int, input().split()))
# for i in range(n):
# print(i+1, ':', sep='', end=' ')
# for j in range(n):
# if i == j:
# continue
# if d[i] < d[j]:
# print('<', end=' ')
# elif d[i] == d[j]:
# print('=', end=' ')
# else:
# print('>', end=' ')
# print()
# d = []
# for i in range(19):
# v = [0] * 19
# v = list(map(int, input().split()))
# d.append(v)
#
# n = int(input())
# for i in range(n):
# x, y = input().split()
# for j in range(19):
# if d[j][int(y)-1] == 0:
# d[j][int(y)-1] = 1
# else:
# d[j][int(y)-1] = 0
#
# if d[int(x)-1][j] == 0:
# d[int(x)-1][j] = 1
# else:
# d[int(x)-1][j] = 0
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()
# h, w = map(int, input().split())
# n = int(input())
# da = []
# for i in range(h):
# v = [0] * w
# da.append(v)
# for i in range(n):
# l, d, x, y = map(int, input().split())
# if d == 0:
# for j in range(l):
# da[x-1][y-1+j] = 1
# else:
# for j in range(l):
# da[x-1+j][y-1] = 1
#
# for i in range(len(da)):
# for j in range(len(da[i])):
# print(da[i][j], end=' ')
# print()
# d = []
# for i in range(10):
# v = [0] * 10
# v = list(map(int, input().split()))
# d.append(v)
#
# x = 1
# y = 1
# if d[x][y] == 2:
# d[1][1] = 9
# else:
# d[1][1] = 9
# while(d[x][y] == 9):
# if d[x][y+1] == 2:
# d[x][y+1] = 9
# break
# elif d[x][y+1] == 0:
# d[x][y+1] = 9
# y = y+1
# else:
# if d[x+1][y] == 2:
# d[x+1][y] = 9
# x = x+1
# break
# elif d[x+1][y] == 0:
# d[x+1][y] = 9
# x = x+1
# else:
# break
#
# for i in range(len(d)):
# for j in range(len(d[i])):
# print(d[i][j], end=' ')
# print()