题目描述

本题使用 Special Judge。

牧场主小C将农场规划为一个 $r$ 行 $c$ 列的网格，其中部分格子被标记为不可通行。Bessie 目前位于左上角 $(1,1)$ 的格子，她想到达右下角 $(r,c)$ 的牛棚去吃晚餐。她知道，从当前位置出发，每次可以向上下左右四个方向中相邻的格子移动一步，一定存在某些可行路径。

这样的路径可能有很多种，请你输出任意一种合法路径，并保证路径上的步数不超过 $10^5$。

输入格式

第一行两个整数 $r,c$，分别表示网格的行数和列数。

接下来 $r$ 行，每行 $c$ 个字符，描述网格中每个格子的状态。

• . 表示 Bessie 可以通过该格子。
• * 表示 Bessie 无法通过该格子。

输出格式

若干行，每行包含两个用空格隔开的整数，表示 Bessie 依次经过的格子坐标。

第一行必须是 1 1，最后一行必须是 r c。

相邻两行的坐标必须是网格中相邻（上下左右）且均可通行的格子。

样例

5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.

1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8

提示

【数据范围】

对于 $100\%$ 的数据，$1\le r\le 113$，$1\le c\le 77$。

答案不唯一，评测使用 Special Judge 校验输出是否合法。