Bovidian 船長冒險營救船員 Beefalo 博士。像所有偉大的冒險一樣，故事發生在表示世界側視圖的二維 $N \times M$ 網格（$1 \le N, M \le 500$）。有些格子為空，有些被阻擋而無法通過。
船長不能跳躍，行動時必須遵守以下物理規則。
若正下方沒有格子（即在網格邊緣），就飛入太空，任務失敗。
若正下方格子為空，就落入該格。
否則： 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,4)。再翻轉落到 (4,4)，右移一次到 (4,5)。最後翻轉落到博士位置 (3,5)。
題目作者：Mark Gordon，2013