Baekjoon-3190-뱀

import math

N = int(input())
K = int(input())
apples = []
for _ in range(K):
    x,y = map(int, input().split())
    apples.append([x-1,y-1])
L = int(input())
dirs = []
for _ in range(L):
    X,C = input().split()
    dirs.append([int(X),C])

class Snake:
    def __init__(self, board_size, apples):
        self.body = [[0,0]]
        self.heading_idx = 0
        self.heading = [0,1]
        self.size = board_size
        self.board = [[0]*board_size for _ in range(board_size)]
        self.is_alive = True

        # board 0: empty, 1: snake, 2: apple
        self.board[0][0] = 1
        for x,y in apples:
            self.board[x][y] = 2

    def rot(self, C):
        if C=='D':
            self.heading_idx = (self.heading_idx + 1) % 4
        else:
            self.heading_idx = (self.heading_idx - 1) % 4
        self.heading = [[0,1],[1,0],[0,-1],[-1,0]][self.heading_idx]
    
    def move(self):
        x,y = self.body[0]
        dx,dy = self.heading[0], self.heading[1]
        nx,ny = x+dx, y+dy
        if 0<=nx<self.size and 0<=ny<self.size:
            if self.board[nx][ny] == 1: # snake
                self.is_alive = False
            elif self.board[nx][ny] == 0: # empty
                self.board[nx][ny] = 1
                rx, ry = self.body[-1]
                self.board[rx][ry] = 0
                self.body.insert(0, [nx,ny])
                del self.body[-1]
            else: # apple
                self.board[nx][ny] = 1
                self.body.insert(0, [nx,ny])
        else:
            self.is_alive = False
    
    def render(self):
        print('-'*self.size)
        for line in self.board:
            print(*line,sep='')
        print('-'*self.size)
    
    def is_end(self):
        return not self.is_alive

snake = Snake(board_size=N, apples=apples)
t = 0
dirs_idx = 0
while True:
    t += 1
    snake.move()
    # snake.render()
    if dirs_idx < len(dirs) and t == dirs[dirs_idx][0]:
        snake.rot(dirs[dirs_idx][1])
        dirs_idx += 1
    if snake.is_end():
        print(t)
        exit()