package bj.gold.l5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
/**
* @author 은서파
* @since 2021. 10. 10.
* @see https://www.acmicpc.net/problem/3190
* @performance 12324 84
* @category #시뮬레이션, #큐
* @memo
* 방향회전을 고려하여 deltas 작성
*/
public class BJ_G5_3190_뱀 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
static StringTokenizer tokens;
static int N, K;
static int [][] map;
static int L;
// 시계 방향으로 회전해야 하므로 북>동>남>서의 순서로 작성!
static int [][] deltas = {{-1, 0},{0, 1},{1, 0},{0, -1}};
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
N = Integer.parseInt(input.readLine());// 보드의 크기
K = Integer.parseInt(input.readLine());// 사과의 개수
map = new int[N+1][N+1];
for(int k=0; k<K; k++) {
tokens = new StringTokenizer(input.readLine());
int r = Integer.parseInt(tokens.nextToken());
int c = Integer.parseInt(tokens.nextToken());
map[r][c]=1;
}// 사과 처리
L = Integer.parseInt(input.readLine());// 회전 정보
int x=0;
String c="";
Snake s = new Snake();
int time = 0;
for(int l=0; l<=L; l++) {
if(l<L) { // 입력으로 들어오는것 처리
tokens = new StringTokenizer(input.readLine());
x = Integer.parseInt(tokens.nextToken());
c = tokens.nextToken();
}else {// 입력 이후의 동작 처리
x = Integer.MAX_VALUE;
}
// x초만큼 이동
while(time<x) {
boolean result = s.move();
time++;
if(!result) {
System.out.println(time);
return;
}
}
// c방향으로 회전
s.turn(c);
}
}
static class Snake extends LinkedList<Point>{
public Snake() {
// 1,1에서 출발하고 방향은 오른쪽!!
addHead(new Point(1, 1));
d = 1;
}
int d;
// 새로운 헤드 추가
public void addHead(Point head) {
this.offer(head);
map[head.r][head.c]=-1;
}
// 이동 - 벽을 만나거나 뱀뱀이를 만나면 끝
// 이동의 주체-head, (마지막에 추가된 녀석)
public boolean move() {
int nr = this.getLast().r + deltas[d][0];
int nc = this.getLast().c + deltas[d][1];
// 이동 가능? 영역 내부이면서 뱀이 아닌 지점 (-1이 아닌 지점)
if(1<=nr && nr<=N && 1<=nc && nc<=N && map[nr][nc]!=-1) {
// 이동하려는 지점이 사과가 아니라면?
if(map[nr][nc]==0) { // 꼬리(맨 처음에 추가된 요소)가 이동 - 감소
Point tail = this.poll();
map[tail.r][tail.c]=0;
}
// 이동 지점 처리
addHead(new Point(nr, nc));
return true;
}else {
return false;
}
}
// 방향전환
public void turn(String c) {
if(c.equals("D")) {
d = (d+1)%4;
}else {
d = (d+3)%4;
}
}
}
static class Point{
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
// REMOVE_START
private static String src = "5\r\n" +
"2\r\n" +
"2 5\r\n" +
"2 4\r\n" +
"6\r\n" +
"4 D\r\n" +
"5 D\r\n" +
"6 D\r\n" +
"7 D\r\n" +
"8 D\r\n" +
"9 D";
// REMOVE_END
}