Barn Navigation

Bessie has gotten herself stuck on the wrong side of Farmer John's barn, and due to her poor vision, she needs help navigating across the barn. The barn is represented by an \(N \times N\) grid (\(2 \le N \le 20\)). Some cells are empty (denoted by a '.') and some contain impassable haybales (denoted by a '*').

Bessie starts at the lower-left corner (cell \(1,1\)) and wants to reach the upper-right corner (cell \(N,N\)). You may issue a sequence of instructions, each being one of the following:
• forward
• turn left 90 degrees
• turn right 90 degrees

If Bessie is instructed to move into a wall or a haybale, she will not move and will simply ignore that command (proceeding to the next one). Once she reaches her goal, she will ignore any remaining instructions.

However, there is a twist: Bessie might start off facing either upward (towards cell \(1,2\)) or rightward (towards cell \(2,1\)). Your task is to produce the shortest sequence of instructions that will guide her to the goal regardless of which starting orientation she has.

Note: The grid is given as \(N\) lines of \(N\) characters. The first line corresponds to the top row and the last line corresponds to the bottom row. Thus, Bessie starts at the bottom-left cell and the goal is at the top-right cell.

inputFormat

The first line contains an integer \(N\) (\(2 \le N \le 20\)). Each of the next \(N\) lines contains a string of \(N\) characters. Each character is either '.' (an empty cell) or '*' (a haybale).

outputFormat

Output the sequence of instructions (one per line) that guides Bessie to the goal regardless of her starting orientation. The instructions must be exactly one of the following strings:
• forward
• turn left 90 degrees
• turn right 90 degrees

sample

2
..
..

forward
turn right 90 degrees
forward
turn left 90 degrees
turn left 90 degrees
forward