CCC Word Hunt

In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order along horizontal, vertical, or diagonal line segments in one of two ways.

Straight: The letters appear consecutively on one line segment.

L‐shaped: The letters appear consecutively on one line segment up to some letter, and then continue on a second line segment that forms a right angle at that letter. In other words, if the target word is of length \(L\), there exists an index \(k\) (with \(1 \le k \le L-2\)) such that the first \(k+1\) letters are in one straight line and the remaining \(L-k\) letters are in another straight line which is perpendicular to the first.

Given a grid of letters and a single word to search for, your task is to determine the total number of times that particular word is hidden in the grid (counting both straight and L-shaped occurrences).

Note: Coordinates in the grid are considered 0-indexed and movements can be made in any of the 8 directions: horizontally, vertically, or diagonally. Any formula appearing here is given in \(\LaTeX\) format.

inputFormat

The input begins with a line containing two integers \(R\) and \(C\) representing the number of rows and columns of the grid respectively.

The next \(R\) lines each contain a string of \(C\) uppercase letters (without spaces) representing the grid.

The final line contains a single word (a string of uppercase letters) to search for.

outputFormat

Output a single integer representing the total number of times the word is hidden in the grid.

sample

3 3
ABC
DEF
GHI
ADG

1