Bessie's Dream Maze

Bessie the cow has wandered into a strange maze in her dream. The maze is formed by an \(N \times M\) grid (with \(1 \le N, M \le 1000\)). She starts at the top-left tile and wants to reach the bottom-right tile. However, each tile has a color with special properties:

• Red: Impassable.
• Pink: Normal tile; Bessie can walk on it.
• Orange: Normal tile; stepping on this tile causes Bessie to smell like oranges.
• Blue: Contains piranhas. Bessie can only pass if she smells like oranges.
• Purple: When Bessie enters a purple tile, she will slide in the direction of her movement until she reaches a non-purple tile or is blocked. Each tile she slides through counts as one move. In addition, purple tiles remove Bessie's orange smell immediately upon contact.

Determine the minimum number of moves Bessie must make to travel from the top-left to the bottom-right tile. If it is impossible, print -1.

inputFormat

The first line contains two integers \(N\) and \(M\). The next \(N\) lines each contain \(M\) strings. Each string is one of: red, pink, orange, blue, or purple, describing the color of that tile. It is guaranteed that the top-left and bottom-right tiles are not red.

outputFormat

Output the minimum number of moves required for Bessie to reach the bottom-right tile. If it is impossible, output -1.

sample

3 3
pink pink pink
pink red pink
pink pink pink

4