Once upon a time in the small town of Mathland, there lived a curious high school student named Tommy. Tommy was passionate about mathematics and always found himself entangled in mathematical mysteries. His favorite subject was calculus, and his enthusiasm for problem-solving often led him to unexpected adventures.

One day, after a particularly challenging calculus class with Mr. T, his calculus teacher, Tommy found himself staying after school to seek additional guidance on a complex integration problem. As Tommy approached Mr. T's desk, he noticed an ancient-looking map spread out with intriguing symbols and patterns.

Curiosity getting the better of him, Tommy asked, "What's that, Mr. T?"

With a mischievous glint in his eye, Mr. T explained, "Tommy, this is the enchanted square maze of Mathland. Legends say that it holds the key to unlocking the deepest secrets of calculus. However, the maze has a rotating nature, and only those who can navigate it wisely will discover its treasures."

Tommy's eyes widened with excitement. Always ready for a challenge, he eagerly embraced the opportunity to navigate the maze presented by Mr. T. Handing him the map, Mr. T conveyed the task at hand, "You must find your way from the entrance E to the exit X along passages marked P, while avoiding impassable walls denoted by W. For each step, You can only move to one of the four orthogonal adjacent position in the maze. The maze rotates ~90~ degrees clockwise every ~K~ steps, but your position does not change. You will be trapped in the maze indefinitely if your current position ends up being a wall. Also, be careful that if the maze rotates on a step, it will do so before you reach your destination for that step. Your math skills will be put to the test!"

Now that you've followed Tommy on his journey to the entrance of the enchanted maze of Mathland, can you calculate the minimum number of steps it took for him to reach the exit X?

Input Specification

The first line contains two integers, ~N~, representing the dimension of the square maze, and ~K~, representing the shifting period.

The next ~N~ lines contain ~N~ characters each, representing the maze grid. Each character is one of E, X, P, or W.

The following table shows how the available ~15~ marks are distributed.

Marks Awarded	~N~	~K~
~6~ marks	~2 \leq N \leq 800~	~K = 2~
~9~ marks	~2 \leq N \leq 800~	~1 \leq K \leq 10~

Output Specification

Output a single integer representing the minimum number of steps required for Tommy to reach the exit X from the entrance E. If it's impossible to reach the exit, output -1.

Sample Input 1

3 1
WWE
WPP
XPP

Sample Output 1

-1

Explanation for Sample 1

Since walls rotate every move, the wall to his left will rotate below him, and the wall on the left edge of the maze will rotate to Tommy's left, trapping him. Therefore, Tommy will immediately get stuck forever.

Sample Input 2

3 3
WWE
WPP
XPP

Sample Output 2

4

Explanation for Sample 2

Tommy is able to go down, then left. Although it appears Tommy is going into a wall, the walls will rotate every ~3~ moves, meaning the wall to the left of Tommy's current position will rotate out of the way. Since there is no wall at the bottom of the grid, Tommy is able to move left. The portal will have rotated to the top left corner. By going up, Tommy has escaped the maze in a total of ~4~ moves.