bj_17837.py

import sys

sys.stdin = open('bj_17837_in.txt', 'r')
input = sys.stdin.readline

n, k = map(int, input().strip().split())
# print(n, k)
field = [list(map(int, input().strip().split())) for _ in range(n)]
# for row in field:
#     print(*row)

chesses = []
chess_field = [[[] for _ in range(n)] for _ in range(n)]
for idx in range(k):
    r, c, direction = map(int, input().strip().split())
    chesses.append([r-1, c-1, direction])
    chess_field[r-1][c-1].append(idx)
# print(chess)

# for row in chess_field:
#     print(row)

dirs = [None, (0, 1), (0, -1), (-1, 0), (1, 0)]
toggle = [None, 2, 1, 4, 3]
turn = 0
while True:
    turn += 1
    # 종료 조건
    if turn > 1000:
        print(-1)
        sys.exit()

    for chess_num in range(k): # idx: 몇번째 말
        r, c, direction = chesses[chess_num]
        # print(r, c, direction)
        #direction: 1,2,3,4 = 우, 좌, 상, 하
        dr, dc = dirs[direction]
        nr = r + dr
        nc = c + dc
        if not(0 <= nr < n and 0 <= nc < n) or field[nr][nc] == 2: #장외 or 파란색
            #방향 전환
            direction = toggle[direction]
            chesses[chess_num][2] = direction
            #이동위치 재 계산
            dr, dc = dirs[direction]
            nr = r + dr
            nc = c + dc

        #체스 이동
        if 0 <= nr < n and 0 <= nc < n and field[nr][nc] != 2: #이동 가능하면

            # 인덱스 찾기
            stack = chess_field[r][c]
            pos = stack.index(chess_num)

            # 이동할 덩어리
            moving = stack[pos:]
            if field[nr][nc] == 1: # 빨간색
                moving = moving[::-1]

            # 덩어리 옮기기
            chess_field[nr][nc].extend(moving)
            if len(chess_field[nr][nc]) >= 4:
                print(turn)
                sys.exit()

            # 옮겨진 덩어리 체스들 위치 업데이트
            for chess in moving:
                chesses[chess][0] = nr
                chesses[chess][1] = nc

            # 기존 덩어리 지우기
            del stack[pos:]



    # print(chess_field)
    # print()