تغامر القبطانة Bovidian لإنقاذ عضوة طاقمها، الدكتورة Beefalo. كما في كل المغامرات العظيمة، يمثل العالم من الجانب بشبكة ثنائية الأبعاد $N \times M$ ($1 \le N, M \le 500$). بعض الخلايا فارغ وبعضها محجوب لا يمكن عبوره.

لا تستطيع القبطانة القفز وتتبع هذه القواعد الفيزيائية.

1. إذا لم توجد خلية أسفلها مباشرة (حافة الشبكة)، تطير إلى الفضاء وتفشل المهمة.

2. إذا كانت الخلية أسفلها فارغة، تسقط فيها.

3. وإلا: a) يمكنها التحرك يسارًا أو يمينًا إذا وجدت الخلية المقابلة وكانت فارغة. b) أو قلب اتجاه الجاذبية.

القلب يبدل «الأسفل» (القاعدتان 1 و2) بين صف رقمه أكبر بواحد وآخر أصغر بواحد. أول صف في الإدخال رقمه 1 وآخر صف $N$. في البداية الأسفل هو الصف الأكبر بواحد.

الدكتورة تائهة. أوصل القبطانة إلى خليتها بأقل عدد من مرات قلب الجاذبية. اطبع -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