הקפטנית 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