You have a grid \(G\) containing \(R\) rows (numbered from \(1\) to \(R\), top to bottom) and \(C\) columns (numbered from \(1\) to \(C\), left to right) of uppercase characters. The character in the \(r^{th}\) row and the \(c^{th}\) column is denoted by \(G_{r, c}\). You also have \(Q\) strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.
An occurrence of string \(S\) in the grid is counted if \(S\) can be constructed by starting at one of the cells in the grid, going right \(0\) or more times, and then going down \(0\) or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string \(S\), you would like to count the number of tuples \(\langle r, c, \Delta r, \Delta c \rangle\) such that:
- \(1 \le r \le R\) and \(r \le r + \Delta r \le R\)
- \(1 \le c \le C\) and \(c \le c + \Delta c \le C\)
- \(S = G_{r, c} G_{r, c + 1} \dots G_{r, c + \Delta c} G_{r + 1, c + \Delta c} \dots G_{r + \Delta r, c + \Delta c}\)
Output
For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.
Note
Explanation for the sample input/output #1
- There are \(2\) occurrences of "ABC", represented by the tuples \(\langle 1, 1, 1, 1 \rangle\) and \(\langle 1, 1, 0, 2 \rangle\).
- There are \(3\) occurrences of "BC", represented by the tuples \(\langle 1, 2, 0, 1 \rangle\), \(\langle 1, 2, 1, 0 \rangle\), and \(\langle 2, 1, 0, 1 \rangle\).
- There is \(1\) occurrence of "BD", represented by the tuple \(\langle 2, 1, 1, 0 \rangle\).
- There is no occurrence of "AC".
- There are \(2\) occurrences of "A", represented by the tuples \(\langle 1, 1, 0, 0 \rangle\) and \(\langle 3, 2, 0, 0 \rangle\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A
|
2
3
1
0
2
|
|
2
|
2 3 3
AAA
AAA
A
AAA
AAAAA
|
6
4
0
|