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,4)。再翻转落到 (4,4)，右移一次到 (4,5)。最后翻转落到博士位置 (3,5)。

题目作者：Mark Gordon，2013