問題
crom君は母親にお使いを頼まれた。
この世界には、crom君の家と二つの店、家と一つ目の店をつなぐ道、一つ目の店と二つ目の店をつなぐ道しか存在しない。
普通におつかいに行ってもつまらないと思ったcrom君は、家から一つ目の店までの距離、一つ目の店から二つ目の店までの距離、おつかいに行って帰ってくるまでの距離を測ることにした。
但し、移動は上下左右しかできないものとする。
入力
h w map0,0 ・・・・・・map0,w-1 ・ ・ ・ ・ maph-1,0・・・・・maph-1,w-1
一行目に、マップの縦、横の長さh,wが与えられる。
二行目から、縦、横の長さがそれぞれh,wのマップの情報が入力される。
マップの情報は以下の通りに与えられる。
- 'H' ： 家
- '.' ： 道
- '#' ： 障害物。ここには移動できない。
- 'S' ： 店
- マップの周りは障害物で囲まれているものとする。
- 店は2つだけ入力され、必ず道と道を結ぶ。
- 家から一つ目の店、一つ目の店から二つ目の店はそれぞれ一本の道で結ばれている。
- 道は一つ目の店を通り、二つ目の店で途切れる。
- 道がどこかでつながるような入力は与えられず、店をつなぐ道と店以外は障害物が入力される。
出力
- 家から一つ目の店までの距離
- 一つ目の店から二つ目の店までの距離
- おつかいに行って帰ってくるまでの距離 を、空白区切りで出力する。
制約
- 4 ≦ h,w ≦ 100
入出力例
入力例1
4 4 #### #SH# #S## ####
出力例1
1 1 4
入力例2
6 9 ######### ######S## #####..## ####.S### ###H.#### #########
出力例2
3 3 12