题目背景

Josip 是一个奇怪的画家。

题目描述

他想画一幅由 $n\times n$ 个像素点组成的画。其中 $n$ 是 $2$ 的幂次（如 $1,2,4,8,16,\dots$）。每个像素点将会被着色为黑色或者白色。Josip 目前已经知道他的理想画作了。

他将按照如下步骤作画：

• 如果整幅画是一个像素点，那么他将依照自己的目标把这个像素点涂成黑色或者白色。

• 否则，他会将正方形分为四个更小的正方形，然后：

1. 从中选择一个正方形全部涂成白色。
2. 再从剩下的三个正方形中选择一个全部涂成黑色。
3. 把剩下的两个正方形当成一幅新的画作，重复上述步骤。

很快他就发现把心目中的画作完完整整的画出来是不可能的。所以，他希望你来编写一个程序，使得画出的一幅画与他心目中的理想画作的差异尽量小。

两张画作之间的差异为颜色不同的像素点的数目。

输入格式

输入第一行为一个整数 $n$，表示画作的边长。

接下来的 $n$ 行，每行 $n$ 个为 $0$ 或 $1$ 的数字，表示理想状态当前像素点为黑色或者白色。

输出格式

输出第一行一个整数，表示最小的差异值。

接下来的 $n$ 行，每行 $n$ 个为 $0$ 或 $1$ 的数字，表示实际上当前像素的颜色。

注意：染色的方案可能有多种，输出任意一种即可，本题使用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

提示

数据规模与约定

• 对于 $50\%$ 的数据，$n\le 8$；
• 对于 $100\%$ 的数据，$1\le n\le 512$。

说明

题目译自 COCI2008-2009 CONTEST #4 T4 SLIKAR。