题目描述

你玩过“拉灯”游戏吗？

16 盏灯排成一个 4×4 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯处于同一行和同一列的灯也会相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

1101
0110
1111
1101

在改变了最左上角的灯的状态后将变成：

0010
1110
0111
0101

给定游戏的初始状态，问：游戏者最少需要几步才能使所有灯打开？

输入格式

输入是一个四行四列的 01 矩阵，其中 0 表示灯开始是关闭的，1 表示灯开始是打开的。数据保证初始状态中存在至少一盏灯开始是关闭的。

输出格式

第一行：一个整数 N，表示游戏者使得所有灯打开所需的最少步数。

接下来 N 行，每行输出两个整数，表示游戏者每一步需要操作的灯的行号、列号。

如果存在多种操作方式，则输出字典序最小的操作方式。所谓字典序最小，是指：假设一共操作了 $K$ 次，第 $i$ 次操作的是第 $X_i$ 行第 $Y_i$ 列的灯，则将 $X_1Y_1X_2Y_2……X_KY_K$ 形成的整数值最小的操作称作字典序最小的操作。

输入样例

1101
0110
1111
1101

输出样例

4
1 2
3 1
3 4
4 2

样例解释

初始状态：

1101
0110
1111
1101

更改第 1 行第 2 列的灯之后，状态为：

0010
0010
1011
1001

更改第 3 行第 1 列的灯之后，状态为：

1010
1010
0100
0001

更改第 3 行第 4 列的灯之后，状态为：

1011
1011
1011
0000

更改第 4 行第 2 列的灯之后，状态为：

1111
1111
1111
1111

形成的操作序列为 12313442 为字典序最小的操作。

数据范围

无。