Portals

A cake sits in a labyrinth and you badly want to eat it. You have a map of the labyrinth, a grid with $R$ rows and $C$ columns. Every cell of the grid holds one of these characters:

• #, a wall block
• ., an open square
• S, the open square you are standing on
• C, the open square with the cake

You walk only on open squares, and you move from one open square to another only when the two squares share a side. Everything outside the rectangle drawn on the map is wall blocks.

To reach the cake faster you got a portal gun. It works like this. At any moment you can fire a portal in one of the four directions up, left, down, right. The portal flies in that direction until it reaches the first wall, and a portal appears on that wall block, on the side that faces you.

At most two portals exist at the same time. If two portals are already placed and you use the gun again, one of them, chosen by you, is removed immediately. Firing a portal at a side that already holds one replaces it. A side of a wall block holds at most one portal, and two portals can sit on different sides of the same wall block.

Once two portals are placed in the labyrinth you can use them to teleport. When you stand on the square next to one of the portals, you walk into it and come out on the open square next to the other portal. This takes as much time as moving between two adjacent squares.

Firing a portal takes no time. Moving between two adjacent squares and teleporting through portals each take one unit of time. A portal stays where it was placed until it is removed, so you can fire a portal, walk somewhere else, and use it from there.

Given the map of the labyrinth together with your starting position and the position of the cake, compute the minimum time you need to reach the cake.

The first line contains two integers, the number of rows $R$ and the number of columns $C$ ($1 \le R, C \le 200$). Each of the next $R$ lines describes one row of the map with $C$ characters, each of them #, ., S or C.

The characters S and C each appear exactly once on the map.

Print one integer, the minimum time needed to reach the cake from the starting position.

Reaching the cake from the starting position is always possible.

In the first example, one of the fastest sequences of moves is this. Move right, move right again, then fire one portal up and one portal down. Walk into the bottom portal, then move one square right and reach the cake.