题目内容

请找出小鲤鱼从当前位置游到小岛边界的最短水路。能游出去就算逃生成功；否则失败。

河流中间有一座小岛，地图用 $r$ 行 $c$ 列的二维矩阵给出。格子里只有 $0$ 和 $1$：$0$ 是水域，$1$ 是陆域。小鲤鱼被困在岛上，只能沿水域向上、下、左、右四格相邻移动，不能走斜线，也不能上陆地。游到矩阵边界上的水域即可回到大河。

小鲤鱼的起点是 $(sx, sy)$。若该格是陆域，视为无法逃生。

最短水路按下面规则确定：

• 先选移动步数最少的路径（步数不含起点）。
• 若最短路径不止一条，选终点坐标更小的：先比行号，行号相同再比列号。
• 若终点也相同，再比较整条路径上所有点的行号之和，取更小者；行号之和仍相同，则取列号之和更小者。
• 不必考虑步数、终点、行号之和、列号之和全部相同的情况。

输入描述

第一行两个整数 $r$、$c$（$3 \le r \le 20$，$3 \le c \le 30$），表示地图的行数和列数。

第二行两个整数 $sx$、$sy$（$0 \le sx < r$，$0 \le sy < c$），表示小鲤鱼当前坐标。

接下来 $r$ 行，每行 $c$ 个整数，元素只为 $0$ 或 $1$：$0$ 表示水域，$1$ 表示陆域。

输出描述

第一行输出最短路径长度 $d$（不含起点）。若无法逃生，输出 $-1$。

若可以逃生，再输出 $d+1$ 行坐标，每行两个整数，用空格分隔，表示路径上依次经过的格子，第一行是起点。

样例1

输入

3 3
1 1
1 1 1
1 0 1
1 1 1

输出

-1

说明

起点在水域，但四周都是陆地，游不到边界。

样例2

输入

3 3
1 1
0 0 0
0 0 0
0 0 0

输出

1
1 1
0 1

说明

起点 $(1,1)$ 四周一格就是边界。四个出口 $(0,1)$、$(1,0)$、$(1,2)$、$(2,1)$ 步数都是 $1$，行号最小的出口是 $(0,1)$，因此向上游一格离开。