Flip It!

Time limit1sMemory limit128 MB

Summary

Simulate a sequence of row and column flips that collapse a grid of cards into one pile, then list the face-up cards from the bottom.

Level: Medium6 of 10
Topics: Simulation, Implementation, Matrix, Recursion
Solved: No attempts yet

Problem

You have a set of cards laid out in an $n$ by $m$ grid. Each card is numbered, and some are face up while others are face down. You can collapse the grid into a single pile using a series of flips. Each flip is one of the following four types:

Top flip: The cards in the top row are flipped over onto the corresponding cards of the row beneath them. A card that was face up becomes face down after the flip, and vice versa. If a cell in the top row holds a pile of cards, the entire pile is flipped over like a stack of pancakes (its order is reversed) as it is moved onto the pile below.
Bottom flip: The same as a top flip, but the bottom row is flipped onto the next-to-bottom row.
Left flip: The cards in the leftmost column are flipped onto the next-to-leftmost column.
Right flip: The cards in the rightmost column are flipped onto the next-to-rightmost column.

After a series of $n + m - 2$ flips, all the cards form a single pile, some face up and some face down. Determine the order of the face-up cards in this final pile.

Input

Each test case starts with a line containing two positive integers $n$ and $m$ , the number of rows and columns in the grid. The next $n$ lines each contain $m$ integers giving the cards' numbers and orientations. (The first line is the top row, and the first value in each line is the leftmost card.) A positive integer $k$ means card $k$ is at that location face up; a negative integer $-k$ means card $k$ is at that location face down ( $k$ is never zero.)

After these $n$ lines comes one more line of $n + m - 2$ characters describing the flips to apply, each being T, B, L, or R for a top, bottom, left, or right flip. Every flip sequence is legal: you are never asked to perform more than $n - 1$ top-and-bottom flips or more than $m - 1$ left-and-right flips. The maximum value of $n$ and $m$ is $20$ .

Input ends with a line containing two zeros.

Output

For each test case, print the case number followed by the numbers of all face-up cards in the final pile, listed starting from the bottom of the pile, in the format shown below.

Case X: c1 c2 ...

If no card ends up face up, print only the case label (for example, Case 2:).

Examples1

Example 1

Input

Expected output

Case 1: 8 6
Case 2:
Case 3: 3