# h, w = map(int, input().split())
# n = int(input())
# data = []
# for i in range(h):
# a = [0] * w
# data.append(a)
#
# for i in range(n):
# l, d, x, y = map(int, input().split())
# for m in range(l):
# if d == 0:
# data[x-1][y+m-1] = 1
# elif d == 1:
# data[x+m-1][y-1] = 1
#
# for i in range(h):
# for j in range(w):
# print(data[i][j], end=' ')
# print()
# data=[]
# for i in range(10):
# v = list(map(int, input().split()))
# x = [0]*10
# data.append(v)
#
# x = 1
# y = 1
# if data[x][y] == 2:
# data[x][y] = 9
# else:
# data[x][y] = 9
# for i in range(20000000):
# if data[x][y+1] == 0:
# y += 1
# data[x][y] = 9
#
# elif data[x][y+1] == 1:
# if data[x + 1][y] == 0:
# x += 1
# data[x][y] = 9
#
# elif data[x + 1][y] == 1:
# break
#
# elif data[x + 1][y] == 2:
# x += 1
# data[x][y] = 9
# break
#
# elif data[x][y+1] == 2:
# y += 1
# data[x][y] = 9
# break
#
# for i in range(10):
# for j in range(10):
# 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
# a = 0
# for i in range(n):
# for j in range(n):
# if (i == 0) or (i == n - 1) or (j == 0) or (j == n - 1):
# a += data[i][j]
#
# print(a)