F. Jupiter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jupiter is home to the largest Coriolis forces in the Solar System. Specifically, the Coriolis force causes horizontal bands on the planet to experience strong winds either East or West. Jupiter has $$$8$$$ of these prominent bands.

Embarking on a mission to navigate Jupiter, you are well aware of winds and need to factor them into the amount of fuel you need to bring on your mission. Your spaceship will enter Jupiter at coordinate $$$S$$$, and need to end at coordinate $$$D$$$. A coordinate can be denoted by the band you are in (vertical position), and the columns (horizontal position) along that band at time $$$t=0$$$.

Each timestep, the Coriolis winds take effect, rotating all positions of even-indexed bands right, and all positions of odd-indexed bands left.

Jupiter also has numerous storms that move along with these bands. You want to avoid these storms at all costs.

Consider the following 4 banded system example, as we can find on Earth: 


        col1   col2   col3   col4   col5
band1 |   .  |   X  |   .  |   D  |   .  | <–
band2 |   X  |   .  |   X  |   X  |   X  | –>
band3 |   .  |   S  |   .  |   .  |   .  | <–
band4 |   .  |   .  |   .  |   .  |   .  | –>

After one timestep, the world would look like:


        col1   col2   col3   col4   col5
band1 |   X  |   .  |   D  |   .  |   .  | <–
band2 |   X  |   X  |   .  |   X  |   X  | –>
band3 |   S  |   .  |   .  |   .  |   .  | <–
band4 |   .  |   .  |   .  |   .  |   .  | –>

Your spaceship lets you move one tile in any cardinal direction (not diagonally) before the Coriolis effect takes effect each timestep. Note you can also choose to not move, in which you move along with the band. Also, note that columns 1 and $$$N$$$ are adjacent, but band1 and band8 are not.

Find the minimum amount of timesteps to travel from coordinate A to coordinate B (if possible) so we can know how much fuel to bring!

Input

The first line contains $$$N$$$, the number of horizontal positions in each band. $$$1 \leq N \leq 3 \cdot 10^3$$$

The next $$$8$$$ lines each contain $$$N$$$ space-separated characters, with each line denoting the state of the world in that band at $$$t=0$$$. The character at the $$$i$$$th position on a line represents column $$$i$$$ in that corresponding band.

  • '.': empty tile
  • 'X': storm tile
  • 'S': start tile
  • 'D': destination tile
Output

Output one integer, representing the minimum amount of timesteps required to travel from start to destination, or -1 if impossible.

Examples
Input
5
X X X X X
X X X X X
. X . D .
X . X X X
. S . . .
. . . . .
X X X X X
X X X X X
Output
2
Input
5
S . . . .
. X X X X
X X . X X
X X X . X
X X X X .
X . X X X
X . X X X
X X X X D
Output
7
Note

For explaining the first sample, let $$$(x,y)$$$ be the coordinate that is in the $$$x$$$th band and the $$$y$$$th column (both $$$1$$$-indexed).

  • At $$$t=0$$$, the bands are as they are in the sample.
  • At $$$t=1$$$, we can move up from $$$(5,2)$$$ to $$$(4,2)$$$. The bands will then move from the Coriolis effect, so we will move to $$$(4,3)$$$, and $$$D$$$ will move to $$$(3,3)$$$.
  • At $$$t=2$$$, we can move up from $$$(4,3)$$$ to $$$(3,3)$$$, arriving at our destination just before the Coriolis effect moves our positions again.

It can be shown this is the fastest way to reach the destination.