Author: Andrew Seidel

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~):

top floor
Key: GW → G GG → W WG → W WW → G
		G	G	W
bottom floor		G	W	W

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 on the right.

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 to the right. 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 Specification

The input 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 \le N \le 8)~ and ~M~ ~(4 \le M \le 1000)~ separated by a space.
• The next ~4~ lines 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 Specification

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

Sample Input

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

Note: Only ~2~ cases are shown in this sample.

ECOO 2017 Question Development Team

Kevin Forest ............................................... Sheridan College
John Ketelaars ....................................... ECOO-CS Communications
Stella Lau .......................................... University of Cambridge
Greg Reid .................. St. Francis Xavier Secondary School, Mississauga
Sam Scott .................................................... Mohawk College
Andrew Seidel ..................... John Fraser Secondary School, Mississauga
David Stermole ............................................ ECOO-CS President
Reyno Tilikaynen ..................................... University of Waterloo

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

---