록키

실베스터 스탤리온은 나이 든 말이다. 마구간 둘레의 밭을 어슬렁거리는 것을 무엇보다 좋아한다. 실베스터는 고집이 세서 앞길에 돌이 없으면 한 방향으로 곧장 걷기만 한다. 바로 앞 칸에 돌이 있으면 다음 세 가지 중 하나를 한다.

1. 오른쪽 칸에 돌이 없으면 오른쪽으로 돌아 그 방향으로 계속 곧장 걷는다.
2. 오른쪽 칸에 돌이 있고 왼쪽 칸에 돌이 없으면 왼쪽으로 돌아 그 방향으로 걷는다.
3. 양쪽 모두 돌이 있으면 뒤로 돌아 왔던 길로 되돌아간다.

여기서 오른쪽과 왼쪽은 실베스터가 지금 향한 방향을 기준으로 한다. 밭 바깥 칸에는 돌이 없다고 본다.

돌이 많은 밭에서는 여러 번 방향을 바꾸다가 뜻밖의 자리로 나가기도 한다. 아래 밭에 실베스터가 $(1, 4)$ 칸으로 들어오면 12칸을 밟고 $(3, 5)$ 칸에서 밭을 빠져나간다. 표의 첫 줄은 열 번호, 각 줄의 맨 앞은 행 번호이고 R는 돌이 놓인 칸이다.

실베스터를 걱정하는 동물 친구가 많다. 특히 절친한 숫양 보는 실베스터의 산책이 어디서 끝나는지 알고 싶어 한다. 밭의 생김새와 실베스터가 들어온 칸이 주어지면, 그가 밭을 빠져나가는 칸과 그때까지 밟는 칸의 수를 구하라.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스는 세 정수 $n$, $m$, $r$로 시작한다. $n$은 밭의 열 개수, $m$은 행 개수, $r$은 돌의 개수이고 $n, m \le 20$이다. 이어서 돌 $r$개의 위치가 c r 꼴로 주어진다. c는 열 번호, r는 행 번호다. 돌의 위치는 공백이나 줄 바꿈으로 구분되며 여러 줄에 걸쳐 주어지기도 한다. 한 칸에 돌이 두 개 이상 놓이는 일은 없다.

돌의 위치 다음에는 실베스터가 들어온 칸이 같은 꼴로 주어진다. 열 번호는 왼쪽에서 오른쪽으로 1부터 $n$까지, 행 번호는 아래에서 위로 1부터 $m$까지 매긴다. 실베스터의 처음 방향은 언제나 그가 들어온 변에 수직이다. 들어온 칸은 모서리 칸이 아니고, 그 칸에 돌은 없다.

세 정수가 모두 0인 줄이 나오면 입력이 끝난다. 주어지는 밭에서 실베스터가 갇히는 일은 없다.

각 테스트 케이스마다 Case x: c r k 꼴로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호, $c$와 $r$는 실베스터가 밭을 빠져나가기 직전에 마지막으로 서 있던 칸의 열과 행, $k$는 산책하는 동안 밟은 칸의 수다. 같은 칸을 여러 번 밟으면 밟은 횟수만큼 센다.