Description

Naganohara Yoimiya 有一个 n×m 的 01 矩阵 A。

Naganohara Yoimiya 喜欢回文，因此她希望 A 中至少有 x 行是回文的，y 列是回文的。

问最少修改多少个位置（一次修改定义为把某个 Ai,j 变为 1−Ai,j）能够达到这一目标。

Input Format

第一行两个正整数 n,m。

接下来 n 行，每行一个长为 m 的 01 串。

Output Format

输出 n+1 行，每行 m+1 个非负整数，第 i 行第 j 个数表示 x=i−1,y=j−1 的答案。

4 2 2 4

5

Hint

Input 1

	

		4 2
2 4
		

			
		

	

Output 1

	

		5
		

			
		

	

Input 2

	

		9 4
3 5 7 8
		

			
		

	

Output 2

	

		4364
		

			
		

	

Input 3

	

		15 6
1 2 6 8 10 14
		

			
		

	

Output 3

	

		330872368
	

数据范围

对于所有数据，保证 1≤m≤n≤21,1≤a1<a2<⋯<am≤n。

测试点编号	n≤	特殊性质
1,2	9	无
3,4,5,6	12	无
7,8	15	无
9,10,11,12	18	无
13,14	21	ai=i
15,16,17,18,19,20	21	无

样例解释

样例 1 解释：以下是所有满足条件的排列 p

	2 1 4 3 2 4 1 3 2 4 3 1 3 2 1 4 3 2 4 1

Source

NOIP模拟题 2024