Baekjoon-17837-새로운 게임 2

N,K = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
horse_board = [[[-1]*3 for _ in range(N)] for _ in range(N)]
dirs = [[0,1],[0,-1],[-1,0],[1,0]]
horses = [list(map(int,input().split()))+[0] for _ in range(K)] # r,c,direction, linked list
for i in range(len(horses)):
    x,y,d,depth = horses[i]
    horses[i] = [x-1,y-1,d-1,depth]
    horse_board[x-1][y-1][0] = i

for t in range(1000):
    for idx in range(len(horses)):
        x,y,d,depth = horses[idx]
        dx,dy = dirs[d]
        nx,ny = x+dx,y+dy

        if not (0<=nx<N and 0<=ny<N) or board[nx][ny]==2: # Blue or out
            if d in [0,1]:
                d = 1-d
            else:
                d = 2+(3-d)
            horses[idx] = [x,y,d,depth]
            dx,dy = dirs[d]
            nx,ny = x+dx,y+dy

        # if t < 3:
        #     print(horses)

        if 0<=nx<N and 0<=ny<N and board[nx][ny]!=2:
            if board[nx][ny]==0: # white
                next_depth = 0
                while next_depth < 3 and horse_board[nx][ny][next_depth]!=-1:
                    next_depth += 1
                for i in range(depth, 3):
                    if horse_board[x][y][i] != -1:
                        if next_depth == 3: # End game
                            print(t+1)
                            exit()
                        horse_board[nx][ny][next_depth] = horse_board[x][y][i]
                        horses[horse_board[x][y][i]] = [nx,ny,horses[horse_board[x][y][i]][2],next_depth]
                        next_depth += 1
                        horse_board[x][y][i] = -1
                    else:
                        break

            elif board[nx][ny]==1: # red
                next_depth = 0
                while next_depth < 3 and horse_board[nx][ny][next_depth]!=-1:
                    next_depth += 1
                max_depth = depth
                while max_depth < 3 and horse_board[x][y][max_depth]!=-1:
                    max_depth += 1
                for i in reversed(range(depth, max_depth)):
                    if horse_board[x][y][i] != -1:
                        if next_depth == 3: # End game
                            print(t+1)
                            exit()
                        horse_board[nx][ny][next_depth] = horse_board[x][y][i]
                        horses[horse_board[x][y][i]] = [nx,ny,horses[horse_board[x][y][i]][2],next_depth]
                        next_depth += 1
                        horse_board[x][y][i] = -1
                    else:
                        break
                    
print(-1)