题目描述

如图所示的$\red{m}$行$\red{n}$列的$\red{0\sim1}$矩阵，其中$\red{0}$表示无障碍，$\red{1}$表示有障碍。设入口为$\red{（1，1）}$，出口为$\red{（m，n）}$，每次移动只能从一个无障碍的单元移到其周围$\red{8}$个方向上任一无障碍的单元，编程给出一条通过迷宫的路径或报告一个“无路”的信息。

输入格式

输入第一行为两个整数，即$\red{m}$和$\red{n（1＜m＜100，1＜n＜100）}$。

以下$\red{m}$行，每行有$\red{n}$个整数，表示$\red{m}$行$\red{n}$列的$\red{0\sim1}$矩阵。

输出格式

顺序输出路径的坐标。若没有路，则输出-1。

样例

输入样例

2 2

0 0

0 0

输出样例

1 1

2 1

2 2

提示

不同的搜索方式，得到的结果不同，所以测试数据仅作参考。