Thuyền trưởng Bovidian phiêu lưu cứu thành viên đoàn, bác sĩ Beefalo. Như mọi cuộc phiêu lưu vĩ đại, thế giới nhìn ngang là lưới hai chiều $N \times M$ ($1 \le N, M \le 500$). Có ô trống và ô bị chặn không thể đi qua.

Không thể nhảy, thuyền trưởng phải theo các luật vật lý sau.

1. Nếu không có ô ngay dưới (mép lưới), cô bay ra không gian và thất bại.

2. Nếu ô ngay dưới trống, cô rơi vào đó.

3. Nếu không: a) Có thể đi trái hoặc phải nếu ô tương ứng tồn tại và trống. b) Hoặc đảo hướng trọng lực.

Đảo chuyển «dưới» (luật 1, 2) giữa hàng có chỉ số lớn hơn một và nhỏ hơn một. Hàng đầu vào đầu tiên là 1, cuối là $N$. Ban đầu hàng lớn hơn một là dưới.

Bác sĩ mất tích. Đến ô của bác sĩ với ít lần đảo nhất. Nếu không thể, in -1.

Dữ liệu vào

• Dòng 1: số nguyên $N$, $M$ cách nhau bởi dấu cách.
• Các dòng $2..1+N$: dòng $i+1$ mô tả hàng $i$. '.' là trống, '#' bị chặn, 'C' là điểm đầu thuyền trưởng, 'D' điểm đầu bác sĩ.

Dữ liệu ra

• Dòng 1: số nguyên, số lần đảo tối thiểu để đến bác sĩ, hoặc -1 nếu không thể.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Ghi chú

Từ (4,2), đảo và rơi đến (2,2), đi phải hai lần tới (2,4). Đảo lần nữa, rơi đến (4,4), đi phải một lần tới (4,5). Cuối cùng đảo và rơi tới bác sĩ ở (3,5).

Tác giả: Mark Gordon, 2013