Problem F

Flipull

You're an orange blob on a ladder on the right of the screen. You fire blocks to the left, which eliminates blocks of the same kind, then flips back the first block of a different kind. The goal is to have at most b blocks left in the game. The game continues until you don't have legal moves. If you still have more than b blocks when the game ends, you lost.

There are 4 kinds of blocks: the blue triangle (T), the pink circle (O), the green square (#) and the cross (X). After firing a block, it keeps flying to the left until it meets a block of a different kind, or reaches a wall. In the former case, the new block is flipped back; in the latter case, the block is reflected and moves down. When moving down, the block flips back the first block of different kind as usual. If the block reaches the bottom wall, it returns to you. Note that each fire must eliminate at least one block, so you can't flip back a block directly by firing at it. As you may guess, a block falls down immediately when the block below it is eliminated, with the help of the gravity. There is also a special magic block which may only appear initially on your hand. It will change into the first block it fires to, so it could be regarded as a sort of 'wildcard' block, as shown in figure 1(a).

The initial blocks always form a square of 4*4, 5*5 or 6*6, on the bottom-left corner of the game. The rows are numbered r1 to r6 from bottom to top, and the columns are numbered c1 to c6 from left to right. There are 12 steps in the ladder (you may convince yourself by counting in figure 1), numbered 1 to 12 from the bottom (the current positions in figure 1) to the top. Since walls can reflect blocks, firing at the 12 steps are actually moving along r1, r2, r3, r4, c1, c1, c1, c1, c2, c3, c4, X in figure 1(a), where X means firing at step 12 will not touch any block (thus an illegal move). Figure 1(b) is a little bit different: pipes can also reflect blocks, so firing at the 12 steps are actually moving along r1, r2, X, r4, X, c1, c1, c1, c1, c2, c3, X. Note that r3 and c4 can never be accessed.

Here is a complete example of how the game illustrated in figure 1(a) is solved (by leaving exactly 3 blocks). Fire four blocks at step 8, 9, 10, 11 (figure 2(a)), then fire at step 10(figure 2(b)) and step 2 (figure 2(c)), finally step 1.

Write a program to solve the game of Flipull with minimal number of fires.

Input

The input consists of at most 50 test cases. Each case begins with a line containing n, b and c (3 < n < 7, 2 < b < n²), where n is the dimension of the initial blocks, b is the maximal number of blocks left, c is the initial block you're holding (M indicates the magic block). The second line contains the name of the game, which contains at most 100 characters and will not contain white characters (spaces and TABs). The next n lines describe the initial blocks (there will never be a magic block inside). The last line contains the target rows/columns for each step. The last case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the name of the game in the first line. The second line should contain a single integer k, the minimal number of fires needed in the first line. The third line should contain k integers from 1 to 12, the step numbers for each fire. Print a blank line after each case. If more than one solution exists, any one is acceptable. It is guaranteed that every puzzle is solvable in no more than 20 moves.

Sample Input

4 3 M
First
XOXO
XOXO
OXOX
#TOX
r1 r2 r3 r4 c1 c1 c1 c1 c2 c3 c4 X
4 3 #
Pipes
TT##
OOTT
TXXX
O#TX
r1 r2 X r4 X c1 c1 c1 c1 c2 c3 X
4 3 T
NoGreedy!!!
X##T
TXXT
TTT#
OXOT
r1 r2 r3 r4 c1 c1 c1 c1 c2 c3 c4 X
4 3 O
Tough...
XOTO
O##O
TXOO
X#TO
r1 r2 r3 r4 c1 c1 c1 c1 c2 c2 c4 X
0

Output for the Sample Input

Case 1: First
7
8 9 10 11 10 2 1

Case 2: Pipes
8
4 11 1 2 1 4 2 2

Case 3: NoGreedy!!!
7
11 4 3 11 2 1 2

Case 4: Tough...
10
1 4 1 3 11 1 4 1 3 2

Rujia Liu's Present 2: A Big Contest of Brute Force