1997 Woburn Computer Programming Challenge

5. Encoding Grid

A kind of grid is cometimes used for encoding messages. Our naval fleet (!) officials decide to use this method of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into 2Nx2N little squares. N² of these little squares are cut out (see figure 1).

Let us briefly describe the encoding process. Take a message of length 4N² characters. Then put an encoding grid onto a blank sheet of paper and beigin to write the first N² letters of the message into the cut-out squares (one letter per square, write letters in the first line from left to right, then in the second line, etc). See figures 2 for the first step in the message "HELLOYELLOWWORLD." After finishing the first step rotate the encoding grid 90 degrees clockwise and continue similarly writing letters. (Figures 3, 4)

After two more steps all of the letters should be written in (figure 5)

O### ##O# O##O ####	H### ##E# L##L ####	#O#Y #### ##E# #L##	HO#Y ##E# L#EL #L##	HOOY LREO LWEL LLDW
fig. 1 the grid	fig. 2 we write in the first 4 letters	fig. 3 we rotate and write the next 4	fig. 4 after we remove the grid	fig. 5 after we write in the rest

It is necessary to have a correctly constructed grid, so that we never get a collision (i.e. we see some alread-written letters through holes in the grid after we rotate). We need to always see N² blank squares after we rotate the grid.

The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately they lost the grid. Fortunately the naval admiral remembered the original text of one of the messages.

Your task is, given this original message text and the filled-in piece of paper with this encoded message, to find one possible correctly constructed grid with which the message text could have been encoded.

Input

The first line of input contains an integer M specifying the number of test cases.
The first line of each test case is N (the encoded message is written on a 2Nx2N grid).
N will be an integer between 1 and 10 inclusive.

The second line of each test case the message which was encoded: a string of 4N² characters.
Each of the next 2N lines contains a string of 2N characters representing the letters in the encoded grid. This grid will contain only letters from "A" to "Z".

Output

The output file should contain one correctly constructed grid for each test case which could have been used to encode the given message into to given grid. The grid should appear in the orientation in which the first N² letters are written. As in figure 1 above, represent uncut parts of the paper with "#" and holes with "O" (the capital letter, not the number). Leave a blank space between the output for each test case; you may leave a trailing blank line at the end of your output file.

Sample Input

2
2
HELLOYELLOWWORLD
HOOY
LREO
LWEL
LLDW
1
SUNK
SU
KN

Sample Output

O###
##O#
O##O
####

O#
##

All Submissions
Best Solutions

Point Value: 20
Time Limit: 10.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...