Captain Bovidian's Gravity Adventure

Captain Bovidian is on an adventure to rescue Doctor Beefalo. The world is represented by an \(N \times M\) grid. Each cell is either empty or blocked. Captain Bovidian cannot jump and must obey the following rules of physics:

• If there is no cell directly underneath her (i.e. if she is at the edge of the grid), she flies into space and fails.
• If the cell directly underneath her is empty, she falls into that cell repeatedly until the cell underneath is blocked.
• If the cell directly underneath her is blocked, she may either move left/right into an empty cell, or flip the direction of gravity.
• When gravity is flipped, the cell considered to be "underneath" toggles between the cell with one higher row index and the cell with one lower row index. Initially, the cell with one higher row index (i.e. downward) is considered underneath.

In the grid, 'C' marks Captain Bovidian's starting position, 'D' marks Doctor Beefalo, '.' indicates an empty cell, and '#' indicates a blocked cell.

Your task is to determine the minimum number of gravity flips required for Captain Bovidian to reach Doctor Beefalo. If it is impossible, output -1.

inputFormat

The first line contains two integers \(N\) and \(M\) (1 \(\le\) N, M \(\le\) 500) — the number of rows and columns of the grid.

Following this, there are N lines each containing M characters representing the grid. It is guaranteed that there is exactly one 'C' and exactly one 'D' in the grid.

outputFormat

Output a single integer — the minimum number of gravity flips required for Captain Bovidian to reach Doctor Beefalo, or -1 if it is impossible.

sample

4 3
###
#C#
#D#
###

0