캔디 랜드

캔디 랜드는 어린이들이 즐겨 하는 보드게임이다. 게임판은 한 줄로 늘어선 여러 칸으로 되어 있고, 각 칸은 색깔 칸이거나 특수 칸이다. 여러 명이 함께 할 수 있다. 플레이어는 차례마다 뒤집혀 쌓인 카드 더미의 맨 위 카드를 뒤집는다. 카드에는 색깔 칸 하나, 같은 색깔 칸 두 개, 또는 특수 칸 하나가 그려져 있다. 색깔 칸 하나가 그려진 카드라면 플레이어는 현재 위치에서 그 색깔의 다음 칸으로 이동한다. 같은 색깔 칸 두 개가 그려진 카드라면 현재 위치를 지나 그 색깔이 두 번째로 나오는 칸으로 이동한다. 특수 칸이 그려진 카드라면 그 특수 칸으로 바로 이동한다. 이 이동은 앞쪽으로도 뒤쪽으로도 될 수 있다. 특수 칸은 보드에 정확히 하나씩만 있다. 여러 플레이어가 같은 칸에 동시에 있을 수 있다. 플레이어는 첫 번째 칸 바로 앞에서 출발한다.

마지막 칸은 모든 색을 가진 칸이며, 카드의 색깔을 가진 다음 칸이 더 없을 때 플레이어가 도착하는 곳이다. 가장 먼저 마지막 칸에 도착한 플레이어가 이긴다. 같은 색깔 칸 두 개가 그려진 카드에서 그 색깔이 마지막 칸에만 있다면, 그 카드를 뽑은 플레이어가 이긴다.

플레이어는 카드를 따라 이동한 뒤, 그 카드를 뒤집힌 상태로 더미 맨 아래에 놓는다. 아이들은 카드를 섞지 않으므로 게임은 완전히 결정적이다.

첫 줄에는 양의 정수 n (2 ≤ n ≤ 200)과 p (2 ≤ p ≤ 6)가 주어진다. n은 칸의 수, p는 플레이어 수이다. 이어지는 n-1개의 줄에는 마지막 칸을 제외한 1번부터 n-1번까지 칸의 내용이 순서대로 한 줄에 하나씩 대문자 문자열로 주어진다. 각 문자열은 대문자 20자 이하이다. 특수 칸은 SPECIAL로 시작하고, 그 뒤에 대문자가 하나 이상 온다. 어떤 색깔 이름에도 SPECIAL이라는 부분 문자열은 없다.

다음 줄에는 카드의 수 c (c ≤ 500)가 주어진다. 이어지는 c개의 줄에는 맨 위 카드부터 한 줄에 카드 한 장씩 주어진다. 카드는 숫자 1, 2, 3 중 하나, 공백, 대문자 문자열로 이루어진다. 1은 색깔 칸 하나, 2는 같은 색깔 칸 두 개, 3은 특수 칸을 뜻한다. 1과 2의 경우 문자열은 보드에 있는 색깔이고, 3의 경우 문자열은 보드에 있는 특수 칸의 이름이다.

이기는 플레이어의 번호를 1부터 시작하는 번호로 한 줄에 출력한다. 입력은 게임이 10,000번 차례 안에 끝나도록 주어진다. 다만 게임을 무한히 계속한다면 일부 플레이어는 끝까지 도착하지 못할 수도 있다.