Description

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.
2. From the remaining three squares, choose one and color it entirely black.
3. 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.

Input Format

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 Format

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.

4
0001
0001
0011
1110

1
0001
0001
0011
1111

4
1111
1111
1111
1111

6
0011
0011
0111
1101

8
01010001
10100011
01010111
10101111
01010111
10100011
01010001
10100000

16
00000001
00000011
00000111
00001111
11110111
11110011
11110001
11110000

Hint

Constraints

• For $50\%$ of the testdata, $n \le 8$.
• For $100\%$ of the testdata, $1 \le n \le 512$.

Notes

Translated from COCI2008-2009 CONTEST #4 T4 SLIKAR.

Translated by ChatGPT 5