Numeric Puzzles Again! 

A different and exciting game is invading all the toy stores around Latin America. It looks the same as a children's jigsaw, but the pieces are constructed entirely using numbers...

The pieces may have non-uniform shapes, but they all must construct a perfect $N \times N$ image. For instance, a 5 $\times 5$ image may be this:

11223
11223
12233
11233
11133

Made with three pieces:

11
11
1
11
111

 22
 22
22
 2

 3
 3
33
33
33

Your problem is to write a program that solves the puzzle using the apropriate pieces.

Notice that once a solution is found, it can be rotated, giving rise to three other solutions. However, a given piece must not be rotated separately in order for you to solve the puzzle.

In addition to the four rotations, a puzzle may have more than one ``true'' solution. You may assume, though, that none of test cases will contain a puzzle with more than one true solution.

Input 

The input file may contain several instances of the problem. Each instance has the following lines, all consecutive in the file:

• One line with an integer giving the side length of the puzzle (at most 20).
• One line with the number of pieces (at most 9).
• Several lines describing the pieces. Each piece is made up of some combination of the same digit (1...9). The pieces are left-aligned, and need not appear in any particular order.

Blank spaces may be used at the beginning of a line and within the pieces in order to define the piece's shape.

Each instance ends with a line containing only the # character. The input file ends with a line containing only the integer 0 (zero).

Output 

You must display the right puzzle as output. In order to find the right puzzle, you must sum the literal values of the rows of each possible rotation of the image and return the image with the largest total sum. For instance, for the puzzle

2 2 3
2 3 3
1 1 3

the sums are: 223 + 233 + 113 = 569, 333 + 231 + 221 = 785, 311 + 332 + 322 = 965 and 122 + 132 + 333 = 587. Thus the right puzzle is

3 1 1
3 3 2
3 2 2

The output of each instance must end with a blank line.

Sample Input 

7
6
3333
33
3333
 33
 33
7  7
7  7
7777
88888
 6
666
 66
  22
222
  2
  5
 55
 55
555
5 5
#
0

Sample Output 

8777333
8733333
8733323
8777323
8655222
6665552
6655555