小雷的好基友

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

又到周末了,小雷在小鲜肉氛围的笼罩下感觉自己more and more old了。想起自己老友的小雷突然想要召集高中老同学(基友)团聚一下。可是他们都不知道山东理工的具体方位(好了,现在我们假设没有任何电子设备,没有GPS,没有百度导航,没有地图,没有路人,没有xxxxxxxx),总之小雷需要去接他们。

小雷在一张地图上标出各同学(基友)的方位。由于美工太差,小雷把淄博市画成了一个n行m列的地图(1 < = n,m < = 1000),地图中小雷在’L’处,他的好基友们在’#’处,其余位置为’.’。小雷现在要把他们一位一位接到山东理工(‘L’处),对于每个位置小雷只能走左右上下四个方向。

出于礼貌,小雷每次只能接一个同学(基友),返回山东理工后才能接下一位,接到最后一位后小雷返回山东理工。小雷有左上近视强迫症。小雷会优先接距离他近的同学,如果距离相同,他会优先接地图里靠左的(横坐标小的),如果靠左程度相同,会优先接靠下的(纵坐标小的),并且小雷会选择最短路线,毕竟懒。。。以最左下为坐标(1,1)

 

Input

多组输入,到EOF结束。对于每组输入:
先输入两个整数n,m(1 < = n,m < = 100),表示地图行与列。

接下来n行每行m个字符。

.表示街道,#表示小雷的好基友,L表示小雷(山东理工)位置。

数据保证没有空格,保证存在小雷。

Output

对于每组输入,先输出两个数k,s表示小雷的同学(基友)数和小雷需要移动的最少步数,之间用空格隔开。
之后k行每行输出(x,y),按顺序输出每次接的同学坐标(1 < = x < = m,1 < = y < = n)。

每组之间输出空行。

Sample Input

3 3
.#.
#L#
.#.
3 3
###
##L
###

Sample Output

4 8
(1,2)
(2,1)
(2,3)
(3,2)

8 30
(2,2)
(3,1)
(3,3)
(1,2)
(2,1)
(2,3)
(1,1)
(1,3)

Hint

 

Source

2015年第五届ACM趣味编程循环赛(第一场) by LeiQ