\(N \times N\) 크기의 격자가 있다. 행과 열은 각각 \(1\) 부터 \(N\) 까지 번호가 매겨져 있으며, 칸 \((r, c)\) 는 \(r\) 번째 행 \(c\) 번째 열을 뜻한다.

뱀은 처음에 칸 \((1, 1)\) 한 칸만을 차지하는 길이 1 로 시작한다. 격자에는 여러 개의 과일이 놓여 있다(과일이 하나도 없을 수도 있다). 시작 칸 \((1, 1)\) 에는 과일이 놓이지 않는다.

이제 \(M\) 개의 이동 명령이 차례대로 주어진다. 각 명령은 U(위), D(아래), L(왼쪽), R(오른쪽) 중 하나이며, 뱀의 머리를 그 방향으로 한 칸 움직인다. 한 번의 이동은 다음과 같이 처리된다.

• 머리가 이동하려는 칸에 과일이 있으면 그 과일을 먹고, 뱀의 길이가 1 늘어난다 (꼬리는 그대로 있고 머리만 새 칸으로 늘어난다). 먹은 과일은 사라진다.

• 과일이 없으면 머리가 새 칸으로 가는 동시에 꼬리가 한 칸 줄어든다(길이는 그대로).

다음 두 경우 중 하나가 발생하면 게임이 그 명령에서 끝난다.

1. 머리가 가려는 칸이 격자 밖이다(벽 충돌).

2. 머리가 가려는 칸이 그 시점에 뱀의 몸이 차지하고 있는 칸이다(자기 몸 충돌). 단, 같은 이동에서 꼬리가 빠져나가는 칸으로는 들어갈 수 있다.

게임이 끝나는 명령의 번호(1부터 시작)를 구하거나, \(M\) 개의 명령을 모두 수행하고도 살아남으면 \(0\) 을 출력하면 된다.

\(1 \le N \le 300\)

\(0 \le K \le N^2 - 1\)

\(0 \le M \le 100{,}000\)

\(1 \le r, c \le N\), 과일 칸은 서로 다르며 \((1, 1)\) 은 과일이 아니다.

첫째 줄에 격자의 한 변의 길이 \(N\) 이 주어진다.

둘째 줄에 과일의 개수 \(K\) 가 주어진다.

다음 \(K\) 개의 줄에는 각각 두 정수 \(r\), \(c\) 가 주어지며, 과일이 놓인 칸 \((r, c)\) 를 의미한다. 같은 칸이 두 번 주어지지 않으며, \((1, 1)\) 은 주어지지 않는다.

그 다음 줄에 이동 명령의 개수 \(M\) 이 주어진다.

마지막 줄에 길이 \(M\) 인 문자열로 이동 명령이 주어진다(각 문자는 U, D, L, R 중 하나). \(M = 0\) 이면 이 줄은 비어 있다.

게임이 끝나는 이동 명령의 번호를 한 줄에 출력한다. 모든 명령을 수행하고도 살아남으면 \(0\) 을 출력한다.

riseoj 작성

출처 Original