Hay un pedazo de cake ubicado en un laberinto y quieres comerlo a toda costa. Tienes un mapa del laberinto, el cual es un tablero de ~R~ filas y ~C~ columnas. Cada celda contiene uno de los siguientes caracteres:

• # denota una pared.
• . denota una celda libre.
• S denota la celda libre actual donde estas.
• C denota la celda libre que tiene el pedazo de cake.

Solo puedes caminar por las celdas libres y moverte de una celda libre a otra si comparten un lado. Además, el área rectangular representada en el mapa está completamente rodeada por bloques de pared.

Para llegar más rápido al pastel, has adquirido una pistola de portales, que funciona de la siguiente manera. En cualquier momento, puedes disparar un portal en una de las cuatro direcciones: arriba, izquierda, abajo y derecha. Cuando se dispara un portal en alguna dirección, volará en esa dirección hasta que alcance la primera pared. Cuando esto sucede, se generará un portal en el bloque de pared, en el lado que te queda de frente.

Como máximo, pueden existir dos portales al mismo tiempo. Si ya se han colocado dos portales en el laberinto, entonces uno de ellos (seleccionado por ti) se eliminará inmediatamente al usar nuevamente la pistola de portales. Disparar un portal a un portal existente lo reemplazará (puede haber como máximo un portal por lado del bloque de pared). Ten en cuenta que puede haber dos portales colocados en diferentes lados del mismo bloque de pared.

Una vez que se colocan dos portales en el laberinto, puedes usarlos para teletransportarte. Cuando estés junto a uno de los portales, puedes caminar hacia él y aparecer en la celda libre junto al otro portal. Hacer esto lleva el mismo tiempo que moverse entre dos celdas adyacentes.

Puedes asumir que disparar portales no lleva tiempo y que moverte entre dos celdas adyacentes o teletransportarte a través de los portales lleva una unidad de tiempo.

Dado el mapa del laberinto, tu posición inicial y la posición del pedazo de cake, calcula el mínimo tiempo necesario para llegar al cake.

Subtareas

• Subtarea 1 (11 puntos): ~1 \leq R \leq 10, 1 \leq C \leq 10~
• Subtarea 2 (20 puntos): ~1 \leq R \leq 50, 1 \leq C \leq 50~
• Subtarea 3 (20 puntos): ~1 \leq R \leq 200, 1 \leq C \leq 200~. Cada celda libre tiene al menos una pared adyacente.
• Subtarea 4 (19 puntos): ~1 \leq R \leq 200, 1 \leq C \leq 200~.
• Subtarea 5 (30 puntos): ~1 \leq R \leq 1000, 1 \leq C \leq 1000~

Entrada

La primera línea de la entrada cotiene dos enteros: el número de filas en el mapa ~R~, y el número de columnas ~C~. Las siguientes ~R~ líneas describen el mapa. Cada una de estas líneas contiene ~C~ caracteres: #, ., S o C.

Se garantiza que S y C aparecen exactamente una vez en el mapa.

Salida

La salida contiene un solo entero - el mínimo tiempo necesario para alcanzar el cake desde la posición inicial.

Se garantiza que siempre es posible alcanzar el cake desde su posición inicial.

Ejemplos

Entrada 1

4 4
.#.C
.#.#
....
S...

Salida 1

4

Una secuencia de movimientos es la siguiente:

1. moverse hacia la derecha.
2. moverse hacia la derecha, disparar un portal arriba y un portal abajo.
3. moverse a través del portal de abajo.
4. moverse un cuadrado a la derecha y llegar al pastel.