Word Search in a Grid

An $N \times M$ grid holds one uppercase letter in each cell. Given a word $S$, write a program that decides whether the word $S$ is in the grid.

The word $S$ is in the grid when you can start at one cell and read the letters of $S$ in order through neighboring cells. The direction can be up, down, left, right, or one of the four diagonals: upper left, upper right, lower left, lower right. The direction must not change partway.

The first line contains the word $S$. The length of $S$ is at most 100, and $S$ consists of uppercase letters only.

The second line contains the number of rows $N$ and the number of columns $M$ of the grid. $N$ and $M$ are natural numbers at most 100.

Each of the next $N$ lines contains the $M$ letters of one row of the grid, with no spaces.

Print 1 if the word $S$ is in the given grid, and 0 if it is not.