1. Wizard's Windows

What is the Problem?

Whizzy the Wizard is trying to decide on which new mage tower to move into. Although each tower is made up of different shapes and sizes, the towers are all completely made of glass. Some of the glass panels are windows (W) that can be opened magically, but some of the glass panels are solid panes of glass (G) in order to provide structural support.

Whizzy has access to every glass panel and he is trying to figure out which panels are windows. Whizzy has gone through two floors of windows and is getting tired of trying to figure out which is which. He is hoping to open the top floor’s windows, so he needs to find a pattern to help him out.

If we lay out a net of each of the towers, they form a net that is N by M in dimension where the width of the building is defined by N and the number of floors in the building is represented by M. A sample diagram as below (assuming N = 3, M = 6):

Whizzy finds that the text written on the front door of the building is a key to figuring out the pattern. An example key is shown below.

To read the key, the letter G represents a support piece of glass, the letter W represents a window. The letter pairs describe what to do to the cell above, based on the two letters surrounding the current position.

For example, take a look at the bottom floor of the tower below. The middle square has a G on the left, and a W on the right. So, according to the first rule in the key (“GW ► G”), the square above it has to be a G. The left-most square is surrounded by a W on the left, (because the tower net wraps around), and a W on the right. So the last rule in the key makes the square above it a G. The right-most square has a W to the left of it, and a G to the right of it, making the square above a W.

Input Specifications

DATA11.txt (DATA12.txt for the second try) will contain 10 towers, each terminated with a line containing a single asterisk. For each tower, the input will be formatted as follows:

• • The first line contains N, (3 ≤ N ≤ 8) and M, (4 ≤ M ≤ 1000) separated by a space.

  • The next 4 lines will contain the rules for moving up the tower, with the left and right side of each rule separated by a space.

  • The next line contains the layout of the bottom floor.

Output Specifications

Output the value of the top floor of the tower as a single, contiguous set of capital letters.

Sample Input (2 towers shown)

3 6

WW G

WG G

GW W

GG W

GWG

*

3 4

WW W

WG W

GW G

GG G

GGW

*

Sample Output

GWW

GGW