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 × N image. For instance, a 5 × 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 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. Your problem is to write a program that solves the puzzle using the apropriate pieces.
2/3 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 223 233 113 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 311 332 322 The output of each instance must end with a blank line. Sample Input 7 6 3333 33 3333 33 33 77 77 7777 88888 6 666 66 22 222 2 5 55 55 555 55
3/3 Sample Output 8777333 8733333 8733323 8777323 8655222 6665552 6655555