P6451 [COCI 2008/2009 #4] SLIKAR

Josip is a strange painter.

He wants to paint a picture made of $n \times n$ pixels, where $n$ is a power of $2$ (such as $1, 2, 4, 8, 16, \dots$). Each pixel will be colored either black or white. Josip already knows what his ideal painting looks like. He will paint following these steps: - If the whole painting is a single pixel, he will color this pixel black or white according to his target. - Otherwise, he will split the square into four smaller squares, and then: 1. Choose one of the squares and color it entirely white. 1. From the remaining three squares, choose one and color it entirely black. 1. Treat the remaining two squares as a new painting and repeat the steps above. Soon he realized that it is impossible to paint his ideal picture exactly. Therefore, he wants you to write a program that makes the painted picture as close as possible to his ideal picture. The difference between two pictures is the number of pixels whose colors are different.

The first line contains an integer $n$, the side length of the picture. The next $n$ lines each contain $n$ digits $0$ or $1$, describing the ideal picture, where each digit indicates whether the corresponding pixel is black or white.

Output one integer on the first line: the minimum possible difference. Then output $n$ lines, each containing $n$ digits $0$ or $1$, describing the actual colors of the pixels. **Note: there may be multiple valid coloring plans. Output any one. This problem uses SPJ.**

#### Constraints - For $50\%$ of the testdata, $n \le 8$. - For $100\%$ of the testdata, $1 \le n \le 512$. #### Notes **Translated from [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #4](https://hsin.hr/coci/archive/2008_2009/contest4_tasks.pdf) *T4 SLIKAR*.** Translated by ChatGPT 5