Soul Gem Game

キュゥべえはなかなか契約を結んでくれない鹿目まどかにしびれを切らせて，ソウルジェムゲームと称して佐倉杏子と美樹さやかのソウルジェムの中身 (魂) を W 列 H 段のロッカーの中に隠してしまった．そこで，まどかは杏子とさやかを助け出したい．しかし，契約を結ばずに助けるにはロッカーボックスの壁を操作して 2 人のソウルジェムの中身を，指定されたロッカーボックスに正しく移さなければならない．ロッカーはロッカーボックスが W 列 H 段に並ぶことで構成され，隣り合うロッカーボックスは壁で仕切られている．

まどかは，1 回の操作でいずれかの隣りあった 2 つのロッカーボックスの壁を取り除くか取り付けることができる．ただし，ロッカーボックスの壁を開けるには制約があり，各ロッカーボックスから隣接する上下左右の壁のうち，高々 2 枚までの壁しか同時に開けておくことはできない．ロッカーボックスには上の段から下の段に向かって重力が働いている．ソウルジェムの中身は液体と同じような動きをし，隣りあった 2 つのロッカーボックスの壁が取り除かれている時，同じ高さであれば互いに同じ量になり，違う高さであれば低い方へ移動する．すべての操作が終わった時に指定された 2 つのロッカーボックスに正しい組み合わせでソウルジェムの中身がすべて入っていればまどかの勝利となる．また，一部のロッカーボックスは穢れており，その中へソウルジェムの中身が入ってしまうと大変なことになってしまうので，そのロッカーボックスはソウルジェムの中身の移動のために使うことはできない．

最小で何度の操作を行えばまどかは 2 人を救いだすことができるかを求めよ．

入力は以下の形式で与えられる．

H W
s11 s12 …s1W
s21 s22 …s2W
…
sH1 sH2 …sHW

H はロッカーの段数，W はロッカーの列数である．sij は上から i 段目の左から j 列目のロッカーボックスの状態を表す．杏子のソウルジェムの中身が入っているときは 'K' であり，さやかのソウルジェムの中身が入っているときは 'S' ，杏子のソウルジェムの中身を移すべきロッカーボックスであるときは 'k'，さやかのソウルジェムの中身を移すべきロッカーボックスであるときは 's'，穢れたロッカーボックスであるときは '#'，それ以外のロッカーボックスであるときは '.' である．

2 人を救い出すために必要な操作の最小回数を出力せよ．どのように操作しても救い出すことが出来ない場合は CONTRACT と出力せよ．

• 1≤H≤10
• 1≤W≤10
• sij は '#', '.', 'S', 'K', 's', 'k' のいずれかである．
• sij = ``'S' であるような i,j がちょうど 1 つだけ存在する．
• sij = ``'K' であるような i,j がちょうど 1 つだけ存在する．
• sij = ``'s' であるような i,j がちょうど 1 つだけ存在する．
• sij = ``'k' であるような i,j がちょうど 1 つだけ存在する．