import sys
input = sys.stdin.readline
n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
check = [[[] * n for _ in range(n)] for _ in range(n)]
piece = []
for i in range(k):
a, b, c = map(int, input().split())
piece.append([a - 1, b - 1, c - 1])
check[a - 1][b - 1].append(i)
#오, 왼, 위, 아래
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
time = 1
flag = 0
while True:
if time > 1000:
print(-1)
break
if flag == 1:
break
for i in range(k):
x, y, d = piece[i]
nx = x + dx[d]
ny = y + dy[d]
#체스판을 벗어나거나, 파랑
if not (0 <= nx < n and 0 <= ny < n) or board[nx][ny] == 2:
d ^= 1
nx = x + dx[d]
ny = y + dy[d]
if not (0 <= nx < n and 0 <= ny < n) or board[nx][ny] == 2:
nx = x
ny = y
#제자리, 방향만 전환
piece[i] = [nx, ny, d]
if nx == x and ny == y:
continue
idx = check[x][y].index(i)
for p in check[x][y][idx + 1:]:
piece[p][0] = nx
piece[p][1] = ny
#흰색
if board[nx][ny] == 0:
check[nx][ny] += check[x][y][idx:]
#빨강
elif board[nx][ny] == 1:
check[nx][ny] += check[x][y][idx:][::-1]
#원래 칸 지우기
check[x][y] = check[x][y][:idx]
if len(check[nx][ny]) > 3:
print(time)
flag = 1
break
time += 1