题目描述

骑着骆驼，在沙尘暴中向前……

Robert 在沙漠中迷路了。由于沙尘暴，他看不清远处。

沙漠可以表示为一个 $N$ 行 $M$ 列的字符矩阵。矩阵中的每个格子表示一种地标，例如金字塔、迷宫遗迹、仙人掌、沙丘等，用一个小写英文字母表示。

为了让 Georgian 判断自己在哪里，Robert 会把当前格子的字母发给 Georgian，然后继续移动以获取更多信息。更准确地说，Robert 从某个任意格子开始，先发送该格子的字母。之后他每次可以向北、东、南、西四个方向之一移动到相邻格子；每进入一个新格子，就发送该格子的字母。Robert 可以多次经过同一个格子，并且每次经过都会发送该格子的字母。

Georgian 发现 Robert 似乎中了诅咒，他发送的字符串总是循环重复的。也就是说，Robert 发送的字符串形如

即字符串 $S$ 连续拼接 $K$ 次。

请帮助 Georgian 判断 Robert 最后可能位于哪些位置。

任务

给定沙漠地图矩阵、字符串 $S$，以及 $Q$ 次询问 $K_i$。

对于每次询问，回答：若 Georgian 收到的字符串是 $S$ 重复 $K_i$ 次，那么 Robert 最后可能位于多少个不同的格子。

称 Robert 最后可能位于某个格子，当且仅当存在一条从任意起点出发、始终不走出矩阵的路径，使得沿途经过格子的字母序列恰好等于 $S$ 重复 $K_i$ 次，并且路径最后停在该格子。

注意：路径的第一个格子也会贡献一个字符，因此若 $|S|=L$，询问 $K$ 对应的路径字符数为 $K\cdot L$。

输入格式

第一行包含两个整数 $N,M$，表示矩阵的行数和列数。

接下来 $N$ 行，每行是一个长度为 $M$ 的小写字母串，表示矩阵的一行。

第 $N+2$ 行包含字符串 $S$。

第 $N+3$ 行包含一个整数 $Q$，表示询问次数。

下一行包含 $Q$ 个整数 $K_1,K_2,\ldots,K_Q$。

输出格式

输出一行，包含 $Q$ 个整数，依次表示每次询问的答案，整数之间用空格分隔。

数据范围与子任务

• $2\le N,M\le 200$；
• $1\le \lvert S\rvert\le 200$；
• $1\le Q\le 100000$；
• $1\le K_i\le 10^9$，对所有 $1\le i\le Q$；
• $K_i\le K_{i+1}$，对所有 $1\le i<Q$。也就是说，询问中的 $K$ 按非降序给出。

样例 1

输入

3 4
cbaz
azzz
bczz
abc
3
1 2 3

输出

2 1 0

解释

第一问中，Robert 观察到字符串 abc。最后他可能位于第 $1$ 行第 $1$ 列，或第 $3$ 行第 $2$ 列，因此答案为 $2$。

第二问中，Robert 观察到字符串 abcabc。最后他只可能位于第 $3$ 行第 $2$ 列，因此答案为 $1$。

第三问中，Robert 观察到字符串 abcabcabc。矩阵中不存在任何格子可以作为结束位置，因此答案为 $0$。

样例 2

输入

1 5
aabaa
aaab
2
1 2

输出

1 1

解释

第一问中，Robert 观察到字符串 aaab。他可以从第 $2$ 列或第 $4$ 列开始，最终都会到达第 $3$ 列，因此答案为 $1$。注意如果从第 $1$ 列或第 $5$ 列开始，则不存在符合该字符串的路径。

第二问中，Robert 观察到字符串 aaabaaab。所有合法路径最终都会到达第 $3$ 列，因此答案仍为 $1$。