지스네이크

알렉스는 스네이크 게임의 열렬한 팬이다.

참고: 이 구글 두들은 아래에서 설명할 스네이크 게임의 규칙과 정확히 일치하지 않는다. 게임이 어떻게 생겼는지 대략적인 모습만 보여 주기 위한 것이다.

알렉스는 이제 막 프로그래밍을 배웠고, 다음 규칙을 따르는 자신만의 스네이크 게임을 개발하려 한다.

• 게임판에는 R개의 행과 C개의 열이 있다. 게임판의 왼쪽 위 칸의 좌표는 (1, 1)이고, 오른쪽 아래 칸의 좌표는 (R, C)이다.

• 게임을 시작할 때, r + c이 홀수인 모든 좌표 (r, c)의 칸에는 먹이가 한 조각씩 있다. 다른 칸에는 먹이가 없다.

• 뱀의 몸은 항상 게임판에서 하나 이상의 칸으로 이루어진 순서가 있고 연결된 수열이다. 이 수열의 첫 번째 칸을 뱀의 "head"라고 한다. 두 번째 칸이 있다면 첫 번째 칸과 모서리만이 아니라 변을 공유하며, 이후의 칸들도 마찬가지이다. 수열의 마지막 칸을 뱀의 "tail"라고 한다.

• 뱀의 머리는 항상 왼쪽, 위쪽, 오른쪽, 아래쪽의 네 방향 중 하나를 향한다.

• 게임을 시작할 때 뱀은 (1, 1) 칸에 있고 길이는 하나이며(즉, 뱀은 머리만으로 이루어져 있다), 머리는 오른쪽을 향한다.

• 각 정수 시각(1초, 2초 등)에 뱀의 머리는 머리가 향하는 방향에 인접한 칸으로 이동한다. 게임판은 순환하므로, 한쪽 가장자리 밖으로 이동하려 하면 머리가 게임판의 반대쪽 가장자리에 나타난다. 예를 들어 뱀이 (1, C)에 있고 머리가 오른쪽을 향한다면, 다음에는 머리가 (1, 1)로 이동한다. 뱀이 (1, C)에 있고 머리가 위쪽을 향한다면, 다음에는 머리가 (R, C)로 이동한다.

• 뱀의 머리가 먹이가 없는 칸으로 이동하면 뱀은 자라지 않는다. 뱀의 두 번째 칸이 있다면 머리가 있던 자리로 이동하고, 세 번째 칸이 있다면 두 번째 칸이 있던 자리로 이동하며, 이후의 칸들도 마찬가지로 이동한다.

• 뱀의 머리가 먹이가 있는 칸으로 이동하면 그 먹이를 먹고(즉, 해당 칸에는 더 이상 먹이가 없다) 몸이 자란다. 먹이가 있던 칸에 새로운 머리가 생긴다. 뱀의 머리였던 칸은 뱀의 두 번째 칸이 되고, 뱀의 두 번째 칸이었던 칸이 있다면 세 번째 칸이 되며, 이후의 칸들도 마찬가지이다.

• 이동이 완료된 뒤 뱀의 머리가 몸을 이루는 다른 칸 중 하나와 같은 위치에 있으면 뱀이 죽고 게임이 즉시 끝난다. (뱀의 머리가 꼬리가 있던 칸을 향해 이동하는 경우에는 이동이 완료되기 전에 꼬리가 비켜나므로 게임이 끝나지 않는다는 점에 유의하라.)

• 게임에서 플레이어는 뱀이 몇 차례 회전 행동을 하게 할 수 있다. 각 행동 $A_{i}$은 $T_{i}$번째 초와 $T_{i}$+1 번째 초 사이에 일어난다. 가능한 행동은 "L"와 "R"의 두 가지이다. "L" 행동은 머리를 왼쪽으로 90도 회전시킨다. 따라서 예를 들어 뱀이 이전에 아래쪽을 향하고 있었다면 행동 후에는 오른쪽을 향한다. "R" 행동은 머리를 오른쪽으로 90도 회전시킨다. 따라서 예를 들어 뱀이 이전에 아래쪽을 향하고 있었다면 행동 후에는 왼쪽을 향한다.

• 게임에는 시간제한이 있다. $10^{9}$번째 초의 이동이 완료된 뒤 게임이 끝난다(게임이 그때까지 계속되었다면!).

게임을 시험하기 위해 알렉스는 일련의 TURN 행동을 작성했다. 주어진 일련의 행동을 시뮬레이션하고 게임이 끝났을 때 뱀의 최종 길이를 알렉스에게 알려 주어야 한다. 이동이 완료된 뒤 뱀의 머리와 몸의 다른 칸이 같은 위치에 놓이거나 시간이 다 되면 게임이 끝날 수 있다는 점을 기억하라. 전자의 경우 길이를 구할 때 머리와 겹치는 몸의 칸을 서로 별개의 두 칸으로 모두 세어야 한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 10.

소규모 데이터 세트(테스트 세트 1 - 공개)

시간제한: 30초. 1 ≤ R, C ≤ 100; 1 ≤ S ≤ 100; 1 ≤ $X_{i}$ ≤ 2000.

대규모 데이터 세트(테스트 세트 2 - 공개)

시간제한: 60초. 1 ≤ R, C ≤ 100000; 1 ≤ S ≤ 100000; 1 ≤ $X_{i}$ ≤ 1000000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 S, R, C로 시작한다. S는 회전 행동의 수이고, R과 C는 각각 게임판의 행과 열의 수를 나타낸다. 이어서 S개의 줄이 주어진다. 이 중 i번째 줄에는 정수 $X_{i}$와, L 또는 R 중 하나인 문자 $A_{i}$가 주어진다. 각 줄은 $X_{i}$번째 초와 $X_{i}$+1 번째 초 사이에 행동을 수행하는 것에 해당한다. 행동은 시간순으로 주어지며, 같은 두 초 사이에 하나보다 많은 행동이 주어지는 일은 절대 없음이 보장된다. 단, 뱀이 이 행동들을 모두 실행하기 전에 게임이 끝날 수도 있다는 점에 유의해야 한다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 게임이 끝났을 때 뱀의 길이이다.