Description

The robot receives $N$ commands, but it does not want to move onto an obstacle or go out of bounds, so it decides to refuse some commands. Find the minimum number of commands it must refuse.

FORWARD move forward by 1.

BACK move backward by 1.

LEFT turn left by 90 degrees.

RIGHT turn right by 90 degrees.

Initially, the robot is facing upwards.

Input Format

The first line contains $M,N,X_0,Y_0$ ($M \le 100, N \le 1000$), meaning the field size is $M\times M$, there are $N$ commands in total, and the starting point is $(X_0,Y_0)$.

Next is an $M\times M$ matrix representing the field. Here . denotes an empty cell, and * denotes an obstacle.

Then follow $N$ lines, each representing one command.

Output Format

Output a single integer: the minimum number of commands to refuse.

4 7 3 3
.***
..**
*..*
****
LEFT
FORWARD
LEFT
BACK
FORWARD
RIGHT
FORWARD

1

Hint

Translated by ChatGPT 5