题目描述

Mitch老鼠在森林里游玩，不小心走进了一个迷宫里面，这个迷宫是一个 $n$ 行 $m$ 列的矩阵，迷宫中有些格子是可以走的，有些格子是不能走的，能走的格子用“o”（小写字母o）表示，不能走的格子用“#”表示。

Mitch选择走出迷宫的策略是：先向右，如果右边走不通则选择向下，如果下边走不通则选择向左，如果左边走不通则选择向上；如果四个方向都走不通，则后退选择其他能走的路径。

Mitch从迷宫的左上角（1,1）点进入迷宫（请注意：入口(1,1)和出口(n,m)点都不是#），请问Mitch有哪些方法可以走出迷宫，走到(n,m)点；请编程求出所有可能的路径，输出这些路径，如果不存在任何的路径可以走出迷宫，请输出“no”。

输入格式

第一行包含两个整数 $n$ 和 $m$，中间用单个空格隔开，代表迷宫的行和列的数量。

接下来 $n$ 行，每行 $m$ 个字符，描述迷宫地图。字符只有“o”或“#”两种，“o”代表这个格子可以走，“#”代表这个格子不能走。

输出格式

按照Mitch选择的走出迷宫的策略，输出所有可能的路径。每条路径的格式为：编号:坐标1->坐标2->...->坐标k（其中编号从1开始，坐标格式为行,列）。如果不存在可行路径，输出“no”。

样例

样例输入 1

6 5
ooooo
o####
ooooo
#oo#o
oooo#
o#ooo

样例输出 1

1:1,1->2,1->3,1->3,2->3,3->4,3->5,3->5,4->6,4->6,5
2:1,1->2,1->3,1->3,2->3,3->4,3->5,3->6,3->6,4->6,5
3:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->5,4->6,4->6,5
4:1,1->2,1->3,1->3,2->3,3->4,3->4,2->5,2->5,3->6,3->6,4->6,5
5:1,1->2,1->3,1->3,2->4,2->4,3->5,3->5,4->6,4->6,5
6:1,1->2,1->3,1->3,2->4,2->4,3->5,3->6,3->6,4->6,5
7:1,1->2,1->3,1->3,2->4,2->5,2->5,3->5,4->6,4->6,5
8:1,1->2,1->3,1->3,2->4,2->5,2->5,3->6,3->6,4->6,5

数据范围

对于 $100\%$ 的数据，$4 \leq n, m \leq 10$。