题目描述

In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways.One way is for the letters of a word to appear on one line segment. The other way is for the letters of a word to appear on one line segment up to some letter and then on a second line segment that forms a right angle at this letter.

Given a grid of letters and a single word to search for, your job is to determine the number of times that particular word is hidden in the grid.

输入格式

The first line of input will contain a string of distinct uppercase letters $W$,representing the word you are to search for in the grid. The length of $W$ will be at least two. The second line of input will be an integer $R(1 \le R \le 100)$, where $R$ is the number of rows in the grid.The third line of input will be an integer $C(1 \le C \le 100)$, where $C$ is the number of columns in the grid.

The remaining input will provide the letters in the grid. It will consist of $R$ lines, where each line contains $C$ uppercase letters separated by single spaces.

输出格式

The following table shows how the available 15 marks are distributed:

The output will consist of a single non-negative integer $H$, representing the number of times the word is hidden in the grid.

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

3

NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

4

提示

本题采用捆绑测试。

• Subtask $1$（$2$ points）：隐藏字符串一定在一条水平线段上。
• Subtask $2$（$2$ points）：隐藏字符串一定在一个水平或垂直线段上。
• Subtask $3$（$2$ points）：隐藏字符串一定在一个水平、垂直或对角线线段上。
• Subtask $4$（$9$ points）：隐藏字符串一定在一个线段或两个互相垂直的线段上。

样例 $1$ 图解：

样例 $2$ 图解：