Consider the puzzle to the right. We only have the sixteen 2 × 2 pieces shown, which we can place and rotate as we wish, as long as the board gets totally covered. There is just one restriction: Adjacent pieces must share the colors at the edges (white with white, black with black).
The puzzle has more than 40 thousand solutions. To order them, we construct a word from every solution, and we sort the words alphabetically. Suppose that we visit a solution by rows, from top to bottom, and each row from left to right. If we write an ‘a’ for every white square, and a ‘b’ for every black square, we get a word with 64 chars. For the solution in the image, the word is
“baabbbbabbbaabbabbbaabbabbbbbaaabbbbbaaabaaaaaaabaaaaaaabaabbbba”.
Input
Input consists of several natural numbers i, each one between 1 and 43616.
Output
For every i, print the i-th solution to the puzzle. Use ‘.’ for white squares and ‘X’ for black squares. Print a line with 10 dashes at the end of each solution.
Input
31057 1 2 43616
Output
X..XXXX. XXX..XX. XXX..XX. XXXXX... XXXXX... X....... X....... X..XXXX. ---------- ........ ...XX..X ...XX..X .XX..XXX .XX..XXX .XX..XXX .XX..XXX .XXXXXX. ---------- ........ ...XX..X ...XX..X .XX..XXX .XX..XXX .XXXXXXX .XXXXXXX .XX..... ---------- XXXXXXXX XXX..XX. XXX..XX. X..XX... X..XX... X..XX... X..XX... X......X ----------