Bovidian 船長は乗組員の Beefalo 博士を救出する冒険中です。すべての大冒険と同様、世界の側面を表す二次元 $N \times M$ 格子（$1 \le N, M \le 500$）が舞台です。空のマスと、塞がれて通れないマスがあります。

船長は跳べず、次の物理規則に従います。

1. 真下にマスがない（格子の端にいる）なら宇宙へ飛び出し、任務は失敗です。

2. 真下が空ならそのマスに落ちます。

3. それ以外なら： a) 対応するマスが存在して空なら左右に動けます。 b) または重力を反転できます。

反転すると「下」（規則1、2）は行番号が1大きいマスと1小さいマスで切り替わります。入力の最初の行は1、最後は $N$。最初は1大きい行が下です。

博士はこの世界で迷っています。最小回数の重力反転で博士のマスに到達させてください。不可能なら -1 を出力してください。

入力

• 1行目：空白区切りの整数 $N$、$M$。
• $2..1+N$ 行目：$i+1$ 行目が世界の $i$ 行目。'.' は空、'#' は障害、'C' は船長の開始位置、'D' は博士の開始位置です。

出力

• 1行目：博士に到達する最小反転回数の整数。不可能なら -1。

入出力例

入力 1

5 5
#####
#...#
#...D
#C...
##.##

出力 1

3

注記

船長は (4,2) から反転して (2,2) に落ち、右2回で (2,4) へ。再反転で (4,4) に落ち、右1回で (4,5) へ。最後に反転して博士の (3,5) に落ちます。

問題作成：Mark Gordon、2013