Robot Command Navigation

You are given a grid of size $$n \times m$$ consisting of cells with values 0 or 1. A cell with a value of 1 represents an open cell and 0 represents a blocked cell. A robot can start from any open cell. Given a command string composed of the characters 'L', 'R', 'U', and 'D' (representing left, right, up, and down moves respectively), determine whether there exists a starting cell such that the robot, when following the command sequence, always remains within the grid and only visits open cells.

For each move, the robot moves one step in the specified direction. If at any point the robot steps outside the grid boundaries or lands on a blocked cell (0), the sequence of commands is not valid for that starting cell.

If there exists at least one valid starting cell from which the robot can execute all commands while staying on open cells, output 1; otherwise, output 0.

inputFormat

The input is read from standard input (stdin) and has the following format:

First line: Two space-separated integers n and m, representing the number of rows and columns of the grid.
Next n lines: Each line contains m space-separated integers (either 0 or 1) describing a row of the grid.
Last line: A string s consisting of characters 'L', 'R', 'U', and 'D' representing the sequence of commands. It may be an empty string.

outputFormat

Print a single integer to standard output (stdout) — 1 if there exists a valid starting cell from which the robot can follow all the commands while staying on open cells, otherwise 0.

3 3
1 1 0
1 0 1
1 1 1
RRDLLU

0