题目描述

你有一个 $2^n\times 2^m$ 的网格，网格从 $0$ 行 $0$ 列开始编号，每个格子上都有一个开关，同时每个格子有两种状态：$0$ 和 $1$，初始时全为 $0$。

按下这个开关会使他和与他八连通的格子状态反转 ，同时假定第 $0$ 行和第 $2^n - 1$ 行相邻，第 $0$ 列和第 $2^m-1$ 列相邻。

求需要按下那些开关使的格子的状态变为目标状态，若无解，输出 $-1$。

输入格式

第一行两个整数，$n$ 和 $m$。

接下来 $2^n$ 行每行 $2^m$ 个整数，表示该格目标状态。

输出格式

若有解，则第一行一个整数，表示需要按下的开关数量 $k$​ 。

接下来 $k$​​ 行，每行两个整数，表示开关位置。

若无解，输出 $-1$。

输入样例 #1

2 2
0 0 1 0
1 1 0 0
1 0 0 1
0 1 0 1

输出样例 #1

3
0 3
1 2
3 1

输入样例 #2

2 3
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

输出样例 #2

15
1 1
1 2
1 4
1 6
1 7
2 1
2 2
2 4
2 6
2 7
3 1
3 2
3 4
3 6
3 7

本组为本站补充样例，不是原卷附件样例。

输入样例 #3

2 2
0 0 1 1
0 0 0 0
0 1 1 1
0 1 0 1

输出样例 #3

11
0 0
0 3
1 0
1 1
1 2
2 1
2 2
2 3
3 0
3 2
3 3

说明提示

【样例 $1$ 解释】

按下 $(0,3)$ 后：

1 0 1 1
1 0 1 1
0 0 0 0
1 0 1 1

按下 $(1,2)$​ 后：

0 1 1 1
0 1 1 1
0 1 1 1
0 0 0 0

按下 $(3,1)$ 后：

1 1 1 0
0 0 0 0
1 1 1 0
1 1 1 0

把三个矩阵异或后就是目标状态。

数据范围