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