뱀

'Dummy'라는 도스 게임이 있다. 이 게임에서는 뱀이 보드 위를 기어 다닌다. 뱀이 사과를 먹으면 길이가 늘어나고, 벽이나 자기 몸에 부딪히면 게임이 끝난다.

게임은 N x N 정사각 보드에서 진행된다. 몇몇 칸에는 사과가 놓여 있고, 보드의 상하좌우 끝은 벽이다. 처음에 뱀은 맨 위 맨 왼쪽 칸에 있으며 길이는 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가 증가하는 순서로 주어진다.

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.