Word Search in a Grid

Interview

Time limit2sMemory limit512 MB

Summary

Decide whether a word appears in a grid along a straight line of neighboring cells in any of the eight directions.

Level: Medium4 of 10
Topics: Array, Simulation, Implementation, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1

Input

ABCD
5 5
ACDBE
ABCED
ACCEE
ACHDF
ACBCE

Expected output

Example 2

Input

STR
6 6
STARTS
STRSTR
RRTSRE
SRSTRR
STRTSR
STSTSS

Expected output

Example 3
Input
```
AFAFK
2 2
AB
CD
```
Expected output
```
0
```
Example 4
Input
```
AAAB
4 4
AAAA
ABBA
ABBA
AAAA
```
Expected output
```
0
```