시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB114605953.636%

문제

로봇 천재 구름이는 연구의 일환으로 A-머신을 제작했다! A-머신은 긴 테이프에 적힌 기호들을 일정한 규칙에 따라 바꾸며 동작하는 기계로, 다음 네 부분으로 이루어져 있다.

  1. 테이프

    $L$개의 칸이 일렬로 연결된 형태로, 각 칸에는 0 또는 1이 쓰여있다. 입력이 주어질 때 테이프는 공백 없이 연속된 문자열로 주어진다.

  2. 헤더

    테이프 위의 칸 하나를 가리키고 있다. 초기 상태에는 테이프의 맨 앞 칸을 가리킨다.

  3. 현재 상태

    머신의 상태를 나타낸다. 상태는 A부터 P까지 16개의 알파벳 대문자 중 하나이다.

  4. 행동표

    $N$개의 규칙으로 이루어져 있다. 각 규칙은 (현재 상태, 읽은 문자, 덮어쓸 문자, 다음 상태, 이동할 방향) 5가지 변수로 이루어져 있다. (현재 상태, 읽은 문자)가 같은 서로 다른 규칙이 주어지지 않는다.

A-머신은 동작 방식은 다음과 같다.

  1. 헤더가 가리키고 있는 칸의 문자를 읽는다.
  2. 만약 (현재 상태, 읽은 문자)가 행동표에 정의되어 있다면, 해당 규칙에 따라 다음 작업을 순서대로 수행한다. 그렇지 않다면 A-머신을 정지한다.
    1. 헤더가 가리키고 있는 칸의 문자를 규칙의 덮어쓸 문자로 덮어쓴다.
    2. 머신의 상태를 규칙의 다음 상태로 바꾼다.
    3. 헤더를 규칙의 이동할 방향으로 움직인다. 이동할 방향이 1이라면 오른쪽으로, -1이라면 왼쪽으로 한 칸 움직이면 된다.
  3. 만약 헤더가 테이프의 왼쪽 끝 또는 오른쪽 끝을 벗어났다면 머신을 정지한다. 그렇지 않다면 1.으로 돌아간다.

구름이는 A-머신의 초기 상태, 테이프에 적힌 문자들의 초기 배열, 머신의 행동표가 주어졌을 때 A-머신이 정지하는지, 정지하지 않고 무한히 동작하는지를 판단하고자 한다. 구름이를 도와 A-머신의 정지 여부를 판단해 주자.

입력

첫 번째 줄에 A-머신의 초기 상태가 주어진다.

두 번째 줄에 행동표의 규칙 개수 $N$과 테이프 길이 $L$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 32$; $1 \leq L \leq 15$)

세 번째 줄부터 $N$개의 줄에 걸쳐 A-머신의 현재 상태, 읽은 문자, 덮어쓸 문자, 다음 상태, 이동할 방향이 공백으로 구분되어 주어진다.

$N+3$ 번째 줄에 길이 $L$의 초기 테이프 문자열이 주어진다.

출력

첫 번째 줄에 A-머신이 정지하면 STOP을, 정지하지 않으면 CONTINUE를 출력하라.

예제 입력 1

A
5 4
A 1 0 A 1
A 0 1 B 1
B 0 1 C -1
C 0 1 C 1
C 1 0 B 1
1001

예제 출력 1

STOP

주어진 A-머신의 행동표는 아래와 같다.

주어진 행동표를 바탕으로 A-머신은 아래와 같이 작동하게 된다. 값이 변하는 부분을 빨간색으로 표시하였다.

마지막 상태에서 헤더의 값이 B이고 테이프의 값은 1인데, 이는 행동표에서 찾을 수 없는 규칙이므로 A-머신은 정지하게 된다.

예제 입력 2

A
2 2
A 1 1 B 1
B 1 1 A -1
11

예제 출력 2

CONTINUE