Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Find String in a Grid

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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}$$$

Input

Input begins with a line containing three integers: $$$R$$$ $$$C$$$ $$$Q$$$ ($$$1 \le R, C \le 500$$$; $$$1 \le Q \le 200\,000$$$) representing the size of the grid and the number of strings, respectively. The next $$$R$$$ lines each contains $$$C$$$ uppercase characters representing the grid. The $$$c^{th}$$$ character on the $$$r^{th}$$$ line is $$$G_{r, c}$$$. The next $$$Q$$$ lines each contains a string $$$S$$$ containing uppercase characters. The length of this string is a positive integer not more than $$$200\,000$$$. The sum of the length of all $$$Q$$$ strings combined is not more than $$$200\,000$$$.

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.

Examples

Input

3 3 5 ABC BCD DAB ABC BC BD AC A

Output

2 3 1 0 2

Input

2 3 3 AAA AAA A AAA AAAAA

Output

6 4 0

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$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/05/2020 23:45:35 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|