'Dummy' ๋ผ๋ ๋์ค๊ฒ์์ด ์๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค.
๊ฒ์์ NxN ์ ์ฌ๊ฐ ๋ณด๋์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋ณด๋์ ์ํ์ข์ฐ ๋์ ๋ฒฝ์ด ์๋ค. ๊ฒ์์ด ์์ํ ๋ ๋ฑ์ ๋งจ์ ๋งจ์ข์ธก์ ์์นํ๊ณ ๋ฑ์ ๊ธธ์ด๋ 1 ์ด๋ค. ๋ฑ์ ์ฒ์์ ์ค๋ฅธ์ชฝ์ ํฅํ๋ค.
๋ฑ์ ๋งค ์ด๋ง๋ค ์ด๋์ ํ๋๋ฐ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ฅธ๋ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๋ค. (2 โค N โค 100) ๋ค์ ์ค์ ์ฌ๊ณผ์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค. (0 โค K โค 100)
๋ค์ K๊ฐ์ ์ค์๋ ์ฌ๊ณผ์ ์์น๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฒซ ๋ฒ์งธ ์ ์๋ ํ, ๋ ๋ฒ์งธ ์ ์๋ ์ด ์์น๋ฅผ ์๋ฏธํ๋ค. ์ฌ๊ณผ์ ์์น๋ ๋ชจ๋ ๋ค๋ฅด๋ฉฐ, ๋งจ ์ ๋งจ ์ข์ธก (1ํ 1์ด) ์๋ ์ฌ๊ณผ๊ฐ ์๋ค.
๋ค์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ํ์ L ์ด ์ฃผ์ด์ง๋ค. (1 โค L โค 100)
๋ค์ L๊ฐ์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ ์ X์ ๋ฌธ์ C๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ. ๊ฒ์ ์์ ์๊ฐ์ผ๋ก๋ถํฐ X์ด๊ฐ ๋๋ ๋ค์ ์ผ์ชฝ(C๊ฐ 'L') ๋๋ ์ค๋ฅธ์ชฝ(C๊ฐ 'D')๋ก 90๋ ๋ฐฉํฅ์ ํ์ ์ํจ๋ค๋ ๋ป์ด๋ค. X๋ 10,000 ์ดํ์ ์์ ์ ์์ด๋ฉฐ, ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ X๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ์ถ๋ ฅํ๋ค.
์ฌ๊ณผ์ ์์น๋ 1ํ 1์ด๋ถํฐ ์์ํ๋ค
# 48ms
N, K = int(input()), int(input())
board = [[0] * N for _ in range(N)]
dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
# ์ฌ๊ณผ๋ 2
for _ in range(K):
i, j = map(int, input().split())
board[i-1][j-1] = 2
L, times = int(input()), []
for _ in range(L):
time, dir = input().split()
times.append((int(time), dir))
def dummy():
dir, now = 0, 1
snake = [(0, 0)]
# ๋ฑ์ 1
board[0][0] = 1
while True:
r, c = snake[-1]
# ์ผ๋จ ๋ชธ ๋๋ฆฌ๊ธฐ
nr, nc = r+dr[dir], c+dc[dir]
# ๋ฑ์ด ๋ฒฝ์ ๋ถ๋ชํ๊ฑฐ๋ ์๊ธฐ ์์ ์ ๋ง๋๊ฒ ๋๋ฉด ๊ฒ์ ์ข
๋ฃ
if (nr<0 or nr>=N or nc<0 or nc>=N) or board[nr][nc] == 1:
return now
# ์ด๋์ ๋ฌด์กฐ๊ฑด ํ๊ธฐ ๋๋ฌธ์ ๋จธ๋ฆฌ๋ ๋ฐ๋์ ์ด๋
snake.append((nr, nc))
# ์ฌ๊ณผ๊ฐ ์๋ ์๋ฆฌ์๋ค๋ฉด ๋จธ๋ฆฌ๊ฐ ์ฐจ์ง
if board[nr][nc] == 2:
board[nr][nc] = 1
# ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ ๋น์์ค
else:
board[nr][nc] = 1
er, ec = snake.pop(0)
board[er][ec] = 0
# ํ ๊ณผ์ ์ด ๋๋ ํ ๋ฐฉํฅ์ด ๋ฐ๋ ๊ฐ๋ฅ์ฑ์ด ์๋ ํ์ธ
if times and now == (change:=times[0])[0]:
if change[1] == 'D':
dir = (dir+1)%4
else:
dir = (dir+3)%4
times.pop(0)
# ๋ชจ๋ ๊ณผ์ ์ด ์ข
๋ฃ๋์ผ๋ 1์ด ์ฆ๊ฐ
now += 1
print(dummy())