再也不依靠任何人

題目敘述

今天Madoka Kaname(鹿目圓)的班上來了一位名子叫做Homura Akemi(曉美焰)轉學生，由於Homura Akemi先天患有心臟疾病，因此看起來非常的虛弱，而且離開學校已久，學業跟不太上，體育也十分的糟糕。放學後她沮喪的走在回家的路上，不過四周的景色越來越奇怪，不知何時，Homura Akem已經陷入了一片漆黑之中，讓她十分驚恐，突然間，一個發亮怪異的生物從前方向她襲擊過來！眼看Homura Akemi就要完蛋了，這時突然跳出了兩個人轟轟轟的把那怪物解決掉了「千鈞一髮呢，要對班上的同學保密喔。」Madoka Kaname拿著一把武器笑著對他說。聽了一翻解釋後，原來她們是魔法少女，與一個像兔子的外星人Kyubey一起行動著。真的很厲害呢，Homura Akemi自此便與Madoka Kaname變的非常親近，希望自己能變的像Madoka Kanam一樣酷，能保護大家。

但在一個月後迎來的$BOSS$魔女的戰役中，這城市的魔法少女紛紛戰死，看著Madoka Kaname的屍體，Homura Akemi絕望的祈禱是否有改變的機會，此時$Kyubey$似乎是聽到了他內心的聲音，「你是否願意賭上你的靈魂來實現你的願望？」$Kyubey$問到，而Homura Akemi堅定的回答，「我希望與Madoka Kaname的相遇重新來過，不是被她保護的我，而是想要成為保護他的我！」契約成立。最後只聽到$Kyubey$的聲音迴盪在腦海中，轉瞬間，Homura Akemi回到了醫院的病床上，身旁堆滿要返回學校要使用的文具。

Homura Akemi發現自己的特殊能力是可以回到過去，不過僅限回到病床上的那一刻，在經常時光之路遊走的她，常常需要在像迷宮的世界徘徊找到唯一的出口，而隨著他進入時光之路的時間不同，他出現的位置就會不太一樣，所以需要記憶很多進入點，如果透露給你時光之路的地圖與進入點，你能幫Homura Akemi算出每個進入點到終點最短的距離是多遠嗎？他會很感謝你的。

然而在每次與$BOSS$魔女的戰役的戰役中，不論以任何方法挽救，Madoka Kaname終究無法逃過戰死或是崩潰成為魔女的結局，悲傷的Homura Akemi只能用他最後的力氣把時間一再的倒轉，希望在所有可能中找出一線生機，到現在，Madoka Kaname在某一次即將轉化為魔女前的最後心願一直迴盪在自己心中「你能不能回到過去又就還沒被$Kyubey$欺騙的那個笨蛋的我，我不想成為魔女。」為了完成他的心願，也是自己成為魔法少女的目的，Homura Akemi親手殺了Madoka Kaname又再次的回到時間的輪迴之中。

輸入說明

只有一筆測資，第一行有兩個整數$N,M$，表示時光之路的大小是$N\times M$的矩形，最左上角的格子編號為$(0,0)$，最右下角的格子編號為$(N−1,M−1)$，接下來有$N$，每行有$M$個字元來描述，其中$#$表示該格子是障礙物無法行走，$\&$表示為起點，$@$表示為終點，剩下的都可子通行，保證有至少一個起點，唯一一個終點。

保證$1 \leq N,M \leq 1000$

輸出說明

對於每個起點按照字典序輸出$Homura Akemi$走到終點的最短路程有多遠，如果走不到請輸出路徑長為$-1$。格式請參考範例。

範例輸入

7 8
@&     #
######  
       #
 #######
       #
###### #
&#&&   #

範例輸出

(0,1) : 1
(6,0) : -1
(6,2) : 28
(6,3) : 27

公告

輸出其數對(x,y) 的字典序，而非輸出文字的字典序
注意IO問題，輸入的換行可能是 \r\n

Judge Setting

run-time limit: 300 ms
memory limit: 13814400 byte
測資數量: 0