Recursive Painting Optimization

Josip wants to paint a picture consisting of n × n pixels where n is a power of two (i.e. \(n=2^k\) for some nonnegative integer \(k\)). Each pixel is either black or white. Josip has already decided his ideal painting, but when following his unique painting procedure, he realizes that he cannot achieve the ideal painting exactly. His painting procedure is as follows:

1. If the entire picture is a single pixel, he colors that pixel exactly as in his target (either black or white).
2. Otherwise, he divides the current square into four equal sub-squares. Then he performs the following steps:
   1. Choose one of the four sub-squares and paint every pixel in it white.
   2. From the remaining three sub-squares, choose one and paint every pixel in it black.
   3. Recursively process the remaining two sub-squares using the same procedure.

The difference between two paintings is defined as the number of pixels whose colors differ. Your task is to produce a painting using the above procedure such that the difference from Josip’s ideal painting is minimized.

Note: You do not have to achieve the optimal difference – any valid painting produced by following the procedure is acceptable. However, a more clever choice in each step may reduce the total difference. In this problem, you are required to implement a method that, given the ideal target configuration, simulates the procedure with a choice of sub-squares that minimizes the number of mismatched pixels.

Hint: For a region of size \(s > 1\), let the four quadrants be numbered as follows:

0: top-left, 1: top-right, 2: bottom-left, 3: bottom-right

You must choose one quadrant to fill white and one (different) quadrant to fill black. The other two quadrants will be processed recursively. For a quadrant that is painted uniformly, the cost is the number of pixels that differ from the target if the entire quadrant is painted in that color.

inputFormat

The first line of input contains an integer n (\(n=2^k\)), the side length of the painting. Each of the next n lines contains a string of n characters. Each character is either '0' (representing white) or '1' (representing black), describing Josip's ideal painting.

outputFormat

Output n lines, each a string of n characters ('0' for white and '1' for black) representing the painting produced by following Josip's procedure.

sample

1
1

1