No left turns#3011
A person in a maze needs to navigate from one cell to another. Each move, they can move to an adjacent cell in one of four directions (up, down, left, or right), but there are specific constraints. The initial direction can be chosen freely. However, after that, it is not allowed to turn back by 180^\circ or make left (90^\circ counterclockwise) turns. Thus, only 90^\circ clockwise turns are allowed. In addition, leaving the boundaries of the maze is not permitted.
Write a program to find the shortest valid path between the given cells.
The first line contains two integers and (1 \leq M, N \leq 1500), the dimensions of the maze. Then follow lines, each containing characters describing the maze. The character indicates a wall (movement into this cell is not allowed), is a free cell, is the cell where the person starts, and is the destination cell. The starting and destination cells are free and occur exactly once each.
Output a single line describing the shortest sequence of moves that will move the person from the starting to the destination cell without making 180^\circ turns or left turns. The character denotes moving up, down, left, and right. If it is not possible to reach the destination cell following the constraints, output NO SOLUTION.
Example 1