G. Pumpkin Patch
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sam is navigating a giant maze of pumpkins, and they need your help to find the exit before it is too late!

The maze can be represented as an $$$n \times m$$$ grid, each cell consisting of one of the following objects:

  • A ".", denoting an empty space.
  • A "P", denoting an impassable pumpkin.
  • A "C", denoting a candy corn, which Sam may collect by passing through.
  • A "J", denoting a jack-o'-lantern, which Sam may only pass through by spending a candy corn (if they currently have no candy corns, it acts as an impassable space).
  • An "S", denoting Sam's starting space.
  • An "E", denoting the exit to the pumpkin patch.

Additionally, Sam can only move in four directions: up, down, left, and right; each taking one unit of time. Given the description of the maze Sam finds themselves in, output the shortest amount it would take for Sam to reach the exit space, our output "SPOOKED!" if it is impossible for Sam to escape.

Input

The input will begin with a single line containing two space-separated integers, $$$n$$$ and $$$m\ (1 \leq n, m \leq 100)$$$. The next $$$n$$$ lines will each contain exactly $$$m$$$ characters, describing the maze. The $$$j^{\text{th}}$$$ character on the $$$i^{\text{th}}$$$ line, denoted as $$$c_{i,j}$$$, satisfies the following requirements:

  • $$$c_{i,j} \in \{$$$"."$$$, $$$"P"$$$, $$$"C"$$$, $$$"J"$$$, $$$"S"$$$, $$$"E"$$$\}$$$.
  • There exists exactly one $$$(i, j) \in \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$$$ such that $$$c_{i,j} = $$$ "S" and exactly one such that $$$c_{i,j} =$$$ "E".

Finally, let $$$d$$$ denote the number of candy corns in the maze, that is, the number of values $$$(i, j)$$$ such that $$$c_{i,j} = C$$$. It is guaranteed that $$$0 \leq d \leq 8$$$.

Output

The output should consist of exactly one line containing either the phrase "SPOOKED!" if it is impossible for Sam to escape, or the minimum amount of time it would take Sam to reach the exit space.

Examples
Input
5 5
S..PC
.PPP.
.P...
.P..J
...JE
Output
16
Input
1 10
SCCCCJJJJE
Output
9
Input
3 3
EJJ
JSJ
JJJ
Output
SPOOKED!